学步园

//floyd+二分答案+最大流判断 

//但是一直wa，改天再详细查查原因。

//后来查出来是构图原因，修改的地方已经在注释中。

//现在AC了。

//我觉得代码写得还算容易看懂吧。

#include<iostream>
using namespace std;
#define MIN(a,b) (a<b?a:b)
const int N=205;
int n,m;
int cow[N],shelt[N];
long long mat[N][N];
const int inf=1<<29;
const long long INF=1ll<<59;
struct Edge
{
	int v,next,re;
	int w;
}edge[N*N*2];
int edgehead[2*N];
int k=1;
int final;
int level[N*2];
bool visit[N*2];
int que[2*N];
void addedge(int u,int v,int w)
{
	edge[k].v=v;
	edge[k].re=k+1;
	edge[k].w=w;
	edge[k].next=edgehead[u];
	edgehead[u]=k++;
	edge[k].v=u;
	edge[k].w=0;
	edge[k].re=k-1;
	edge[k].next=edgehead[v];
	edgehead[v]=k++;
}
long long floyd()
{
	long long ret=0;
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				if(mat[i][j]>mat[i][k]+mat[k][j])
				{
					mat[i][j]=mat[i][k]+mat[k][j];
				}
				if(mat[i][j]>ret&&mat[i][j]!=INF)
					ret=mat[i][j];
			}
	return ret;
}
bool bfs()
{
	memset(visit,0,sizeof(visit));
	memset(level,0,sizeof(level));
	visit[0]=true;
	level[0]=0;
	int head=1,tail=1;
	que[tail++]=0;
	while(head<tail)
	{
		int now=que[head++];
		if(now==final)
		{
			return true;
		}
		for(int i=edgehead[now];i;i=edge[i].next)
		{
			int v=edge[i].v;
			if(!visit[v]&&edge[i].w>0)
			{
				level[v]=level[now]+1;
				visit[v]=true;
				que[tail++]=v;
			}
		}
	}
	return false;
}
int dinic(int now,int sum)
{
	if(now==final)
		return sum;
	int os=sum;
	for(int i=edgehead[now];i&∑>0;i=edge[i].next)
	{
		int v=edge[i].v;
		if(level[v]==level[now]+1&&edge[i].w>0)
		{
			int tmp=dinic(v,MIN(edge[i].w,sum));
			edge[i].w-=tmp;
			edge[edge[i].re].w+=tmp;
			sum-=tmp;
		}
	}
	return os-sum;
}
bool make(long long len)
{
	k=1;
	memset(edge,0,sizeof(edge));
	memset(edgehead,0,sizeof(edgehead));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)//for(int j=i;j<=n;j++)
		{
			if(mat[i][j]<=len)
			{
				addedge(i,n+j,inf);
			}
		}
	for(int i=1;i<=n;i++)
	{
		addedge(0,i,cow[i]);
		addedge(i+n,final,shelt[i]);
	}
	int ans=0;
	while(bfs())
	{
		ans+=dinic(0,inf);
	}
	if(ans<cow[0])
	{
		return false;
	}
	else
	{
		return true;
	}
}
int main()
{
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(cow,0,sizeof(cow));
		memset(shelt,0,sizeof(cow));
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
				mat[i][j]=mat[j][i]=INF;
		final=2*n+1;
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&cow[i],&shelt[i]);
			cow[0]+=cow[i];
		}
		int from,to;
		long long dis;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&from,&to);
			scanf("%lld",&dis);
			if(mat[from][to]>dis)
			{
				mat[to][from]=mat[from][to]=dis;
			}
		}
		long long s=0,l;
		l=floyd()+1;
		long long ans=-1;
		while(s<l)
		{
			long long mid=(s+l)/2;
			if(make(mid))
			{
				ans=l=mid;
			}
			else
			{
				s=mid+1;
			}
		}
		printf("%lld\n",ans);
	}	
	return 0;
}