#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <cmath>
using namespace std;
#define V 500
#define E 200000
#define inf 1000100000
struct Edge{
	long long u,v,c,next;
}edge[E*2];
long long cnt,dist[V],head[V],que[V],sta[V];
long long f,p,sum,ox[250],maxx[250],map[250][250],ll,rr,mid;
long long dinic(long long s,long long t){
   	long long ans=0;
    while(true){
        long long left,right,u,v;
        memset(dist,-1,sizeof(dist));
        left=right=0;
        que[right++]=s;
        dist[s]=0;
        while(left<right){
            u=que[left++];
            for(int k=head[u];k!=-1;k=edge[k].next){
                u=edge[k].u;
                v=edge[k].v;
                if(edge[k].c>0 && dist[v]==-1){
                    dist[v]=dist[u]+1;
                    que[right++]=v;
                    if(v==t){
                        left=right;
                        break;
                    }
                }
            }
        }
        if(dist[t]==-1) break;
        long long top=0;
        long long now=s;
        while(true){
            if(now!=t){
                long long k;
                for(k=head[now];k!=-1;k=edge[k].next){
                    if(edge[k].c>0 && dist[edge[k].u]+1==dist[edge[k].v]) break;
                }
                if(k!=-1){
                    sta[top++]=k;
                    now=edge[k].v;
                }
                else{
                    if(top==0) break;
                    dist[edge[sta[--top]].v]=-1;
                    now=edge[sta[top]].u;
                }
            }
            else{
                int flow=inf,ebreak;
                for(int i=0;i<top;i++){
                    if(flow>edge[sta[i]].c){
                        flow=edge[sta[i]].c;
                        ebreak=i;
                    }
                }
                ans+=flow;
                for(int i=0;i<top;i++){
                    edge[sta[i]].c-=flow;
                    edge[sta[i]^1].c+=flow;
                }
                now=edge[sta[ebreak]].u;
                top=ebreak;
            }
        }
    }
    return ans;
}
void UFset(){
    cnt=0;
    memset(head,-1,sizeof(head));
}
void addedge(long long u,long long v,long long c){
    edge[cnt].u=u;edge[cnt].v=v;edge[cnt].c=c;
    edge[cnt].next=head[u];head[u]=cnt++;
    edge[cnt].u=v;edge[cnt].v=u;edge[cnt].c=0;
    edge[cnt].next=head[v];head[v]=cnt++;
}
bool init(){
	sum=0;
	long long b=0;
	for(int i=1;i<=f;i++){
		cin>>ox[i]>>maxx[i];
		sum+=ox[i];
		b+=maxx[i];
	}
	for(int i=1;i<=f;i++)
		for(int j=1;j<=f;j++)
			map[i][j]=inf;
	for(int i=1;i<=f;i++)
		map[i][i]=0;
	while(p--){
		long long x,y,z;
		cin>>x>>y>>z;
		map[x][y]=map[y][x]=map[x][y]>z?z:map[x][y];
	}
	if(sum>b)
		return 0;
	return 1;
}
void floyd(){
	rr=-1;
	for(int i=1;i<=f;i++)
		for(int j=1;j<=f;j++)
			for(int k=1;k<=f;k++){
				if(map[i][k]!=inf&&map[j][i]!=inf&&(map[j][k]>(map[j][i]+map[i][k])||map[j][k]==inf))
					map[j][k]=(map[j][i]+map[i][k]);
				if(map[j][k]!=inf)
					rr=map[j][k]>rr?map[j][k]:rr;
			}
}
void setedge(int mid){
	UFset();
	for(int i=1;i<=f;i++)
		addedge(0,i,ox[i]);
	for(int i=1+f;i<=f*2;i++)
		addedge(i,2*f+1,maxx[i-f]);
	for(int i=1;i<=f;i++)
		for(int j=1;j<=f;j++)
			if(map[i][j]<=mid)
				addedge(i,j+f,inf);
}
void sol(){
	ll=0;
	rr+=1;
	long long flag=-1;
	while(ll<=rr){
		mid=(ll+rr)/2;
		setedge(mid);
		if(dinic(0,2*f+1)==sum){
			flag=mid;
			rr=mid-1;
		}
		else
			ll=mid+1;
	//	cout<<"flag"<<flag<<"   "<<"mid"<<mid<<endl;
	}
	cout<<flag<<endl;
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    while(cin>>f>>p){
        if(!init()){
			cout<<"-1"<<endl;
			continue;	
		}
        floyd();
        sol();
    }
    return 0;
}