1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <cassert>
  8 #include <cstdio>
  9 #include <bitset>
 10 #include <vector>
 11 #include <deque>
 12 #include <queue>
 13 #include <stack>
 14 #include <ctime>
 15 #include <set>
 16 #include <map>
 17 #include <cmath>
 18 using namespace std;
 19 
 20 typedef struct Edge {
 21     int u, v, w, next;
 22 }Edge;
 23 
 24 const int inf = 0x7f7f7f7f;
 25 const int maxn = 20200;
 26 const int maxm = 200200;
 27 int cnt, dhead[maxn];
 28 int cur[maxn], dd[maxn];
 29 Edge dedge[maxm<<3];
 30 int S, T, N;
 31 
 32 void init() {
 33     memset(dhead, -1, sizeof(dhead));
 34     for(int i = 0; i < maxn; i++) dedge[i].next = -1;
 35     S = 0; cnt = 0;
 36 }
 37 
 38 void adde(int u, int v, int w, int c1=0) {
 39     dedge[cnt].u = u; dedge[cnt].v = v; dedge[cnt].w = w; 
 40     dedge[cnt].next = dhead[u]; dhead[u] = cnt++;
 41     dedge[cnt].u = v; dedge[cnt].v = u; dedge[cnt].w = c1; 
 42     dedge[cnt].next = dhead[v]; dhead[v] = cnt++;
 43 }
 44 
 45 bool bfs(int s, int t, int n) {
 46     queue<int> q;
 47     for(int i = 0; i < n; i++) dd[i] = inf;
 48     dd[s] = 0;
 49     q.push(s);
 50     while(!q.empty()) {
 51         int u = q.front(); q.pop();
 52         for(int i = dhead[u]; ~i; i = dedge[i].next) {
 53             if(dd[dedge[i].v] > dd[u] + 1 && dedge[i].w > 0) {
 54                 dd[dedge[i].v] = dd[u] + 1;
 55                 if(dedge[i].v == t) return 1;
 56                 q.push(dedge[i].v);
 57             }
 58         }
 59     }
 60     return 0;
 61 }
 62 
 63 int dinic(int s, int t, int n) {
 64     int st[maxn], top;
 65     int u;
 66     int flow = 0;
 67     while(bfs(s, t, n)) {
 68         for(int i = 0; i < n; i++) cur[i] = dhead[i];
 69         u = s; top = 0;
 70         while(cur[s] != -1) {
 71             if(u == t) {
 72                 int tp = inf;
 73                 for(int i = top - 1; i >= 0; i--) {
 74                     tp = min(tp, dedge[st[i]].w);
 75                 }
 76                 flow += tp;
 77                 for(int i = top - 1; i >= 0; i--) {
 78                     dedge[st[i]].w -= tp;
 79                     dedge[st[i] ^ 1].w += tp;
 80                     if(dedge[st[i]].w == 0) top = i;
 81                 }
 82                 u = dedge[st[top]].u;
 83             }
 84             else if(cur[u] != -1 && dedge[cur[u]].w > 0 && dd[u] + 1 == dd[dedge[cur[u]].v]) {
 85                 st[top++] = cur[u];
 86                 u = dedge[cur[u]].v;
 87             }
 88             else {
 89                 while(u != s && cur[u] == -1) {
 90                     u = dedge[st[--top]].u;
 91                 }
 92                 cur[u] = dedge[cur[u]].next;
 93             }
 94         }
 95     }
 96     return flow;
 97 }
 98 
 99 int n, m;
100 int a, b, w;
101 
102 int main() {
103     // freopen("in", "r", stdin);
104     while(~scanf("%d%d",&n,&m)) {
105         init();
106         S = 0, T = n + 1, N = T + 1;
107         for(int i = 0; i < n; i++) {
108             scanf("%d%d",&a,&b);
109             adde(S, i+1, a);
110             adde(i+1, T, b);
111         }
112         for(int i = 0; i < m; i++) {
113             scanf("%d%d%d",&a,&b,&w);
114             adde(a, b, w);
115             adde(b, a, w);
116         }
117         printf("%d\n", dinic(S,T,N));
118     }
119     return 0;
120 }