#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<set>#include<map>#include<stack>#include<vector>#include<queue>#include<string>#include<sstream>#define eps 1e-9#define ALL(x) x.begin(),x.end()#define INS(x) inserter(x,x.begin())#define FOR(i,j,k) for(int i=j;i<=k;i++)#define MAXN 20010#define MAXM 1800000#define INF 0x3fffffffusing namespace std;typedef long long LL;int i,j,k,n,m,x,y,T,ans,big,cas,w;bool flag;struct Edge{	int u,v,weight;	int next;}edge[MAXM];int head[MAXN];	/* head[u]表示顶点u第一条邻接边的序号, 若head[u] = -1, u没有邻接边 */int	current;	/* 当前有多少条边 */void add_edge(int u, int v, int weight) {	/* 添加正向边u->v */	edge[current].u = u;	edge[current].v = v;	edge[current].weight = weight;	edge[current].next = head[u];	head[u] = current++;	/* 添加反向边v->u */	edge[current].u = v;	edge[current].v = u;	edge[current].weight = 0;	edge[current].next = head[v];	head[v] = current++;}int isap(int s, int e) {	int	i,u,v,max_flow,aug,min_lev;	/* 寻找增广路径的过程中, curedge[u]保存的是对于顶点u当前遍历的边, 寻找顶点u的邻接边时不用每次	 * 都从head[u]开始找, 而是从curedge[u]开始找, 这样就减少了搜索次数	 * 当增广路径找到后	 * curedge保存的就是一条增广路径了, 比如	 * 0---四-->1---六-->2--七--->3---八--->4 0,1,2,3,4是顶点号, 四六七八是边的序号	 * curedge[0] = 四, curedge[1] = 六, ... curedge[3] = 8, curedge[i]即保存找过的轨迹 	 */	int	curedge[MAXN],parent[MAXN],level[MAXN];	/* count[l]表示对于属于层次l的顶点个数, 如果某个层次没有顶点了, 	 * 就出现断层, 意味着没有增广路径了, 这就是gap优化, 可以提前结束寻找过程 	 * augment[v]表示从源点到顶点v中允许的最大流量, 即这条路线的最小权重	 */	int count[MAXN],augment[MAXN];	memset(level,0,sizeof(level));	memset(count,0,sizeof(count));	//初始时每个顶点都从第一条边开始找	for (i=0;i<=n;i++)	{		curedge[i] = head[i];	}	max_flow=0;	augment[s]=INF;	parent[s]=-1;	u=s;	while (level[s]<n)	/* 不能写成level[s] < MAX_INT */	{		if (u==e)		/* 找到一条增广路径 */		{			max_flow+=augment[e];			aug=augment[e];			//debug("找到一条增广路径, augment = %d\n", aug);			//debug("%d", e);			for (v=parent[e];v!=-1;v=parent[v])	/* 从后往前遍历路径 */			{				i=curedge[v];				//debug("<--%d", v);				edge[i].weight-=aug;				edge[i^1].weight+=aug;	/* 如果i是偶数, i^1 = i+1, 如果i是奇数, i^1 = i-1 */				augment[edge[i].v]-=aug;				if (edge[i].weight==0) u=v;	/* u指向增广后最后可达的顶点, 下次就从它继续找 */			}			//debug("\n");		}		/* 从顶点u往下找邻接点 */		for (i=curedge[u];i!=-1;i=edge[i].next)	/* 从curedge[u]开始找, 而不是head[u]从头开始, curedge[u]保存的是上次找过的边 */		{			v=edge[i].v;			if (edge[i].weight>0 && level[u]==(level[v]+1))	/* 找到一条边就停止 */			{				augment[v]=min(augment[u],edge[i].weight);				curedge[u]=i;				parent[v]=u;				u=v;				break;			}		}		if (i==-1) 	/* 没有邻接点, 回溯到上一个点 */		{			if (--count[level[u]]==0) 			{				//debug("顶点%d在level %d断层\n", u, level[u]);//GAP优化 				break;			}			curedge[u]=head[u];	/* 顶点u的所有边都试过了,没有出路, 更新了u的level后, 又从第一条边开始找 */			//找出level最小的邻接点			min_lev=n;			for (i=head[u];i!=-1;i=edge[i].next) 			{				if (edge[i].weight>0) 				{					min_lev=min(level[edge[i].v],min_lev);				}			}			level[u]=min_lev+1;			count[level[u]]++;			//debug("顶点%d的level= %d\n", u, level[u]);			//debug("顶点%d走不通, 回到%d\n", u, edge[curedge[u]].u);			if (u!=s) u=parent[u];	/* 回退到上一个顶点 */		}	}	return max_flow;}int main(){    int m,u,v,w,a,b;    while (scanf("%d %d",&n,&m)!=EOF)    {        memset(edge,0,sizeof(edge));        memset(head,-1,sizeof(head));        current=0;        for (u=1;u<=n;u++)        {            scanf("%d %d",&a,&b);            add_edge(0,u,a);            add_edge(u,n+1,b);        }        while (m--)        {            scanf("%d %d %d",&u,&v,&w);            /* 如果调用函数添加边, 速度明显边慢 */            //add_edge(u, v, w);            //add_edge(v, u, w);             /* 添加正向边u->v */            edge[current].u = u;            edge[current].v = v;            edge[current].weight = w;            edge[current].next = head[u];            head[u] = current++;            /* 添加反向边v->u */            edge[current].u = v;            edge[current].v = u;            edge[current].weight = w;            edge[current].next = head[v];            head[v] = current++;        }        n+=2;        printf("%d\n",isap(0,n-1));    }    return 0;}