#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
ll n,m,s,t,hav[100005],can[100005],f[205][205];
ll dep[100005],head[100005],tot=1;
struct Edge{
    ll to,w,nxt;
}edge[100005];
void Add(ll u,ll v,ll w){
    edge[++tot].to=v;
    edge[tot].w=w;
    edge[tot].nxt=head[u];
    head[u]=tot;
}
void add(ll u,ll v,ll w){
    Add(u,v,w); Add(v,u,0);
}
bool bfs(ll s){
    memset(dep,0,sizeof(dep));
    queue<ll>Q; Q.push(s); dep[s]=1;
    while(!Q.empty()){
        ll x=Q.front(); Q.pop();
        for(ll i=head[x];i;i=edge[i].nxt){
            ll tmp=edge[i].to;
            if(dep[tmp] || !edge[i].w) continue;
            dep[tmp]=dep[x]+1;
            Q.push(tmp);
        }
    }
    return dep[t];
}
ll dfs(ll x,ll stream){
    if(x==t) return stream;
    ll ouf=0;
    for(ll i=head[x];i;i=edge[i].nxt){
        ll tmp=edge[i].to;
        if(dep[tmp]!=dep[x]+1 || !edge[i].w) continue;
        ll flow=dfs(tmp,min(stream,edge[i].w));
        stream-=flow; ouf+=flow;
        edge[i].w-=flow; edge[i^1].w+=flow;
    }
    if(!ouf) dep[x]=0;
    return ouf;
}
ll all=0;
bool check(ll mid){
    memset(head,0,sizeof(head)); tot=1;
    for(ll i=1;i<=n;i++)
        add(s,i,hav[i]), add(i+n,t,can[i]);
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=n;j++){
            if(f[i][j]<=mid) add(i,j+n,2e18);
        }
    ll ans=0;
    while(bfs(s)) ans+=dfs(s,2e18);
    return ans==all;
}
int main(){
    cin>>n>>m;
    s=2*n+1, t=2*n+2;
    for(ll i=1;i<=n;i++)
        for(ll j=1;j<=n;j++) f[i][j]=1e18;
    for(ll i=1;i<=n;i++){
        cin>>hav[i]>>can[i]; all+=hav[i];
        f[i][i]=0;
    }
    for(ll i=1;i<=m;i++){
        ll u,v,w; cin>>u>>v>>w;
        f[u][v]=f[v][u]=min(f[u][v],w);
    }
    ll lft=0, rht=0, ans=-1;
    for(ll k=1;k<=n;k++)
        for(ll i=1;i<=n;i++)
            for(ll j=1;j<=n;j++)
            if(i!=k && j!=k && i!=j && f[i][k]<1e18 && f[k][j]<1e18)
            {f[i][j]=min(f[i][k]+f[k][j],f[i][j]); if(f[i][j]<1e18) rht=max(rht,f[i][j]);}
    while(lft<=rht){
        ll mid=lft+rht>>1;
        if(check(mid)){
            ans=mid;
            rht=mid-1;
        }else lft=mid+1;
    }
    cout<<ans<<endl;
}