#include<cstdio>
#include<cstring>
typedef long long LL;
const LL N=2005;
const LL M=50005;
LL MAX=0;
int n,m,st1,ed1;
int A[N],B[N];
LL map[N][N];
struct qq
{
	int x,y;
	int other;
	LL z;
	int last;
};
qq s[M*2];
int num=0,last[N];
int h[N];
int q[N];//循环队列
LL min (LL x,LL y)
{
	if (x==-1) return y;
	if (y==-1) return x;
	return x<y?x:y;
}
bool bt ()
{
	memset(h,0,sizeof(h));
	int st=1,ed=2;
	q[st]=st1;h[st1]=1;
	while (st!=ed)
	{
		int x=q[st];
		for (int u=last[x];u!=-1;u=s[u].last)
		{
			int y=s[u].y;
			if (s[u].z>0&&h[y]==0)
			{
				h[y]=h[x]+1;
				q[ed]=y;
				ed++;
				if (ed>=N) ed=1;
			}
		}
		st++;
		if (st>=N) st=1;
	}
//	for (int u=1;u<=ed1;u++) printf("%d ",h[u]);
	if (h[ed1]==0) return false;
	return true;
}
LL find (int x,LL f)
{
	//printf("YES");
	if (x==ed1) return f;
	LL s1=0,t;
	for (int u=last[x];u!=-1;u=s[u].last)
	{
		int y=s[u].y;
		if (s[u].z>0&&h[y]==(h[x]+1)&&s1<f)
		{
			t=find(y,min(s[u].z,f-s1));
			s1+=t;
			s[u].z-=t;
			s[s[u].other].z+=t;
		}
	}
	if (s1==0) h[x]=0;
	return s1;
}
int init1 (int x,int y,LL z)
{
	num++;
	s[num].x=x;
	s[num].y=y;
	s[num].z=z;
	s[num].last=last[x];
	last[x]=num;
	return num;
}
void init (int x,int y,LL z)
{
	int num1=init1(x,y,z),num2=init1(y,x,0);
	s[num1].other=num2;
	s[num2].other=num1;
}
LL check (LL x)
{
	num=0;memset(last,-1,sizeof(last));
	for (int u=1;u<=n;u++) init(st1,u,A[u]);
	for (int i=1;i<=n;i++) init(i+n,ed1,B[i]);
	for (int u=1;u<=n;u++) init(u,u+n,MAX);
	for (int u=1;u<=n;u++)
		for (int i=1;i<=n;i++)
			if (map[u][i]!=-1&&map[u][i]<=x)
				init(u,i+n,MAX);
	/*printf("%d",num);
	printf("=======================");
	for (int u=1;u<=num;u++)
		printf("%d %d %I64d\n",s[u].x,s[u].y,s[u].z);
	printf("=======================");
	getchar();getchar();*/
	LL ans=0;
	while (bt()==true)
		ans=ans+find(st1,MAX);
	return ans;
}
int main()
{
	memset(map,-1,sizeof(map));
	scanf("%d%d",&n,&m);
	st1=2*n+1;ed1=st1+1;
	for (int u=1;u<=n;u++)
	{
		scanf("%d%d",&A[u],&B[u]);
		MAX+=A[u];
	}
	for (int u=1;u<=m;u++)
	{
		int x,y;
		LL z;
		scanf("%d%d%I64d",&x,&y,&z);
		/*printf("z:%I64d\n",z);
		printf("%I64d %I64d\n",map[x][y],z);*/
		map[x][y]=min(map[x][y],z);
		map[y][x]=map[x][y];
	}
	for (int k=1;k<=n;k++)
	{
		for (int u=1;u<=n;u++)
		{
			if (u==k) continue;
			for (int i=1;i<=n;i++)
			{
				if (i==u||i==k) continue;
				if (map[u][k]==-1||map[k][i]==-1) continue;
				map[u][i]=min(map[u][i],map[u][k]+map[k][i]);
			}
		}
	}
	/*for (int u=1;u<=n;u++)
	{
		for (int i=1;i<=n;i++)
			printf("%I64d ",map[u][i]);
		printf("\n");
	}*/
	LL l=1,r,ans=-1,mid;
	r=LL(1000000000)*LL(n);
	while(l<=r)
	{
		mid=(l+r)/2;
		if(check(mid)==MAX)
		{
			r=mid-1;
			ans=mid; 
		}
		else 
			l=mid+1;
	}
	printf("%I64d\n",ans);
	return 0;
}