#include<stdio.h> #include<string.h> const int maxn = 20100; const int maxm = 200200; const int inf = 1<<29; struct node { int v, c, next; }edge[maxm*6]; int head[maxn], tot; int n, m; void init() { int i; for(i = 0; i <= n+2; i++) head[i] = -1; tot = 0; } void add(int s, int t, int c) { edge[tot].v = t; edge[tot].c = c; edge[tot].next = head[s]; head[s] = tot++; edge[tot].v = s; edge[tot].c = 0; edge[tot].next = head[t]; head[t] = tot++; } int gap[maxn], dis[maxn], cur[maxn], pre[maxn]; int sap(int s, int t, int vs) { bool flag; int i; for(i = 0; i <= vs; i++) { cur[i] = head[i]; gap[i] = dis[i] = 0; } gap[0] = vs; int u = pre[s] = s, maxf = 0, aug = inf, v; while(dis[s] < vs) { loop: for(i = cur[u]; i != -1; i = edge[i].next) { v = edge[i].v; if(edge[i].c > 0 && dis[u] == dis[v] + 1) { flag = 1; if(edge[i].c < aug) aug = edge[i].c; pre[v] = u; cur[u] = i; u = v; if(u == t) { maxf += aug; while(u != s) { u = pre[u]; edge[cur[u]].c -= aug; edge[cur[u]^1].c += aug; } aug = inf; } goto loop; } } int min_d = vs; for(i = head[u]; i != -1; i = edge[i].next) { v = edge[i].v; if(edge[i].c > 0 && dis[v] < min_d) { min_d = dis[v]; cur[u] = i; } } if(!(--gap[dis[u]])) break; ++gap[dis[u] = min_d + 1]; u = pre[u]; } return maxf; } int main() { int i, j; int x, y, z; scanf("%d%d", &n, &m); init(); int S = 0, T = n+1; for(i = 1; i <= n; i++) { scanf("%d%d", &x, &y); add(S, i, x); add(i, T, y); } for(i = 1; i <= m; i++) { scanf("%d%d%d", &x, &y, &z); add(x, y, z); add(y, x, z); } printf("%d\n", sap(S, T, n+2)); return 0; }