#include<cstdio>
#include<cstring>
#include<cstdlib>
typedef long long LL;
const LL N=2100;
const LL M=50000;
LL max=0;
int a[N],b[N];
LL map[N][N];
int p,f,sst,eed;
struct tree{LL z;int x,y,next,other;
}sa[M*2];
int len,first[N*2];
LL min(LL x,LL y)
{
	if(x==-1) return y;
	if(y==-1) return x;
	if(x<y) return x;
	return y;
}
void ins(int x,int y,LL z)
{
	len++;
	sa[len].x=x;
	sa[len].y=y;
	sa[len].z=z;
	sa[len].next=first[x];
	first[x]=len;
	sa[len].other=len+1;
	len++;
	sa[len].x=y;
	sa[len].y=x;
	sa[len].z=0;
	sa[len].next=first[y];
	first[y]=len;
	sa[len].other=len-1;
}
int h[N],tr[M];
bool build()
{
	int st=1,ed=2;
	tr[1]=sst;
	memset(h,0,sizeof(h));
	h[sst]=1;
	while(st!=ed)
	{
		int x=tr[st];
		for(int i=first[x];i!=0;i=sa[i].next)
		{
			int y=sa[i].y;
			if(sa[i].z>0&&h[y]==0)
			{
				h[y]=h[x]+1;
				tr[ed]=y;
				ed++;
				if(ed>=M-1) ed=1;
			}
		}
		st++;
		if(st>=M-1) st=1;
	}
	if(h[eed]!=0) return true;
	return false;
}
LL find(int x,LL f)
{
	if(x==eed) return f;
	LL s=0,o;
	for(int i=first[x];i!=0;i=sa[i].next)
	{
		int y=sa[i].y;
		if(sa[i].z>0&&h[y]==(h[x]+1)&&s<f)
		{
			o=find(y,min(f-s,sa[i].z));
			s+=o;
			sa[i].z-=o;
			sa[sa[i].other].z+=o;
		}
	}
	if(s==0) h[x]==0;
	return s;
}
LL check(LL x)
{
	
	len=0;
	memset(first,0,sizeof(first));
	for(int i=1;i<=f;i++) ins(sst,i,a[i]);
	for(int i=1;i<=f;i++) ins(i+f,eed,b[i]);
	for(int i=1;i<=f;i++) ins(i,i+f,max);
	for(int i=1;i<=f;i++)
	{
		for(int u=1;u<=f;u++)
		{
			if(map[i][u]!=-1&&map[i][u]<=x)
			ins(i,u+f,max);
		}
	}//printf("1");
   LL ans=0;
	while(build()==true)
	{
		ans+=find(sst,max);
	}
	return ans; 
}
int main()
{
//freopen("Ombro.in","r",stdin);
//	freopen("Ombro.out","w",stdout);
	memset(map,-1,sizeof(map));
	scanf("%d%d",&f,&p);
	for(int i=1;i<=f;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		max+=a[i];
	}
	int x,y;
	LL z;
	for(int i=1;i<=p;i++)
	{
		scanf("%d%d%I64d",&x,&y,&z);
		map[x][y]=min(map[x][y],z);
		map[y][x]=map[x][y];
	}
	sst=f*2+1;eed=sst+1;
	for(int i=1;i<=f;i++)
	{
		for(int u=1;u<=f;u++)
		{
			if(u==i) continue;
			for(int j=1;j<=f;j++)
			{
				if(j==i||j==u) continue;
				if(map[u][i]==-1||map[i][j]==-1) continue;
				map[u][j]=min(map[u][i]+map[i][j],map[u][j]);
			}
		}
	}
	LL l=1,r,mid,ans=-1;
	r=LL(1000000000)*LL(f);
	while(l<=r)
	{
		mid=(l+r)/2;
	    if(check(mid)==max)
		{
			ans=mid;
			r=mid-1;
			}	
			else l=mid+1;
	}
	printf("%I64d\n",ans);
	return 0;
}