Maxflow

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
#define MAXN 20005
#define MAXE 480005
#define INF 1234567890
 
using namespace std;
 
int n,m;
int totaledge,v[MAXE],next[MAXE],cap[MAXE],point[MAXN];
int ss,st;
int level[MAXN],cur[MAXN];
queue<int> q;
 
void addedge(int x,int y,int z1,int z2){
    int i;
    i = ++totaledge;
    v[i] = y;
    cap[i] = z1;
    next[i] = point[x];
    point[x] = i;
    i = ++totaledge;
    v[i] = x;
    cap[i] = z2;
    next[i] = point[y];
    point[y] = i;
}
 
int bfs(){
    int i,x;
    memset(level,0,sizeof(level));
    while (!q.empty()) q.pop();
    level[ss] = 1;
    cur[ss] = point[ss];
    q.push(ss);
    while (!q.empty()){
        x = q.front();
        q.pop();
        for (i=point[x];i;i=next[i])
            if (cap[i]>0 && level[v[i]]==0){
                level[v[i]] = level[x]+1;
                cur[v[i]] = point[v[i]];
                if (v[i]==st) return 1;
                q.push(v[i]);
            }
    }
    return 0;
}
 
int dfs(int x,int y){
    if (x==st) return y;
    int i,j,k;
    k = 0;
    for (i=cur[x];i;i=next[i]){
        cur[x] = i;
        if (cap[i]>0 && level[v[i]]==level[x]+1){
            j = dfs(v[i],min(y-k,cap[i]));
            cap[i] -= j;
            cap[i^1] += j;
            k += j;
            if (k==y) break;
        }
    }
    return k;
}
 
int dinic(){
    int i,j;
    i = 0;
    while (bfs()) do{
        j = dfs(ss,INF);
        i += j;
        //printf("%d\n",j);
    }   while (j>0);
    return i;
}
 
int main(){
    int i,x,y,z;
    scanf("%d%d",&n,&m);
    ss = n + 1;
    st = n + 2;
    memset(point,0,sizeof(point));
    totaledge = 1;
    for (i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        addedge(ss,i,x,0);
        addedge(i,st,y,0);
    }
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z,z);
    }
    printf("%d\n",dinic());
    return 0;
}