#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;

#define MIN(a,b) (a<b?a:b)

const int size=505;
long long inf=1<<28;

struct field_struct
{
	int cow_num;
	int shelter;
};
field_struct field[size];

struct road_struct
{
	int to;
	int iter;
	long long cap;
};
road_struct road[500005];

long long dis[size][size],stack[size*size],stack_num,temp[size*size];
int n,m,total,k,st,ed;
int city[size],h[size],gap[size];

inline void add_road(const int &from,const int &to,const long long &value)
{
	road[k].cap=value;
	road[k].to=to;
	road[k].iter=city[from];
	city[from]=k++;

	road[k].cap=0;
	road[k].to=from;
	road[k].iter=city[to];
	city[to]=k++;
}

void build_graph(long long mid)
{
	int i,j;
	k=0;
	ed=total=n*2+2;
	st=total-1;

	memset(city,-1,sizeof(city));
	for(i=1;i<=n;i++)
	{
		if(field[i].cow_num!=0)
			add_road(st,i,field[i].cow_num);
		if(field[i].shelter!=0)
			add_road(i+n,ed,field[i].shelter);
		add_road(i,i+n,inf);
	}

	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(dis[i][j]!=-1&&dis[i][j]<=mid)
			{
				add_road(i,j+n,inf);
				add_road(j,i+n,inf);
			}
}

long long search(int now,long long flow)
{
	if(now==ed)
		return flow;
	int iter,to,pre=total-1;
	long long ans=flow,cap,temp;

	for(iter=city[now];iter!=-1;iter=road[iter].iter)
	{
		to=road[iter].to;
		cap=road[iter].cap;

		if(cap>0)
		{
			if(h[to]+1==h[now])
			{
				temp=search(to,MIN(ans,cap));
				road[iter].cap-=temp;
				road[iter^1].cap+=temp;
				ans-=temp;

				if(h[st]>=total)
					return flow-ans;
				if(ans<=0)
					break;
			}
			if(h[to]<pre)
				pre=h[to];
		}
	}

	if(ans==flow)
	{
		gap[h[now]]--;
		if(gap[h[now]]==0)
			h[st]=total;
		h[now]=pre+1;
		gap[h[now]]++;
	}

	return flow-ans;
}

long long SAP()
{
	long long ans=0;

	memset(h,0,sizeof(h));
	memset(gap,0,sizeof(gap));

	gap[st]=total;
	while(h[st]<total)
		ans+=search(st,inf);
	return ans;
}

int main()
{
	while(scanf("%d%d",&n,&m)==2)
	{
		int i,j,l;
		int from,to;
		long long value,temp_num=0;
		long long left,right,mid,ans=0;
		bool found=false;
		inf*=inf;

		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&field[i].cow_num,&field[i].shelter);
			ans+=field[i].cow_num;
		}

		memset(dis,-1,sizeof(dis));
		while(m--)
		{
			scanf("%d%d%lld",&from,&to,&value);
			if(dis[from][to]==-1||dis[from][to]>value)
				dis[from][to]=dis[to][from]=value;
		}

		for(l=1;l<=n;l++)
			for(i=1;i<=n;i++)
				if(dis[i][l]!=-1)
					for(j=1;j<=n;j++)
						if(dis[l][j]!=-1)
							if(dis[i][j]==-1||dis[i][j]>dis[i][l]+dis[l][j])
								dis[i][j]=dis[i][l]+dis[l][j];
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(dis[i][j]!=-1)
					temp[temp_num++]=dis[i][j];
		sort(temp,temp+temp_num);
		
		stack_num=0;
		stack[stack_num++]=temp[0];
		for(i=1;i<temp_num;i++)
			if(temp[i]!=temp[i-1])
				stack[stack_num++]=temp[i];
		left=0,right=stack_num-1;
		while(left<right)
		{
			mid=(left+right)/2;
			build_graph(stack[mid]);
			if(SAP()==ans)
			{
				found=true;
				right=mid-1;
			}
			else left=mid+1;
		}

		if(found)
			printf("%lld\n",stack[right+1]);
		else printf("-1\n");
	}
	return 0;
}