题意：

思路：

先Floyd一遍两两点之间的最短路 二分答案

建图

跑Dinic

只要不像我一样作死#define int long long 估计都没啥事……

我T到死辣……..

最后才改过来……

（不过注意一哈 答案 &最短路确实是会爆int的）

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 667

int f,m,xx,yy,cow[222],cap[222],zz,all;

long long map[222][222],maxx;

struct Dinic{

    int first[N],next[N*1000],v[N*1000],tot,vis[N],w[N*1000],q[N*1000],head,tail;

    void init(){

        memset(first,-1,sizeof(first)),tot=0;

    }

    void add(int x,int y,int z){

        w[tot]=z,v[tot]=y,next[tot]=first[x],first[x]=tot++;

        w[tot]=0,v[tot]=x,next[tot]=first[y],first[y]=tot++;

    }

    bool tell(){

        head=0,tail=1;

        memset(vis,-1,sizeof(vis));

        vis[0]=0,q[0]=0;

        while(head<tail){

            int t=q[head++];

            for(int i=first[t];~i;i=next[i])

                if(vis[v[i]]==-1&&w[i])

                    vis[v[i]]=vis[t]+1,q[tail++]=v[i];

        }

        return vis[666]!=-1;

    }

    int flow(int x,int y){

        if(x==666)return y;

        int r=0;

        for(int i=first[x];~i&&y>r;i=next[i])

            if(w[i]&&vis[v[i]]==vis[x]+1){

                int t=flow(v[i],min(y-r,w[i]));

                w[i]-=t,w[i^1]+=t,r+=t;

            }

        if(!r)vis[x]=-1;

        return r;

    }

    int work(){

        int ans=0,jy;

        while(tell())while(jy=flow(0,0x3fffffff))ans+=jy;

        return ans;

    }

    bool check(long long x){

        init();

        for(int i=1;i<=f;i++)add(0,i,cow[i]),add(i+f,666,cap[i]);

        for(int i=1;i<=f;i++)

            for(int j=1;j<=f;j++)

                if(map[i][j]<=x)

                    add(i,j+f,0x3fffffff);

        return work()==all;

    }

}dinic;

signed main(){

    memset(map,0x3f,sizeof(map));

    scanf("%d%d",&f,&m);

    for(int i=1;i<=f;i++)map[i][i]=0;

    for(int i=1;i<=f;i++)scanf("%d%d",&cow[i],&cap[i]),all+=cow[i];

    for(int i=1;i<=m;i++){

        scanf("%d%d%d",&xx,&yy,&zz);

        map[xx][yy]=min(map[xx][yy],(long long)zz),map[yy][xx]=map[xx][yy];

    }

    for(int k=1;k<=f;k++)

        for(int i=1;i<=f;i++)

            for(int j=1;j<=f;j++){

                map[i][j]=min(map[i][j],map[i][k]+map[k][j]);

                if(map[i][j]<=1000000000LL*200)maxx=max(maxx,map[i][j]);

            }

    long long l=0,r=maxx,ans=-1;

    while(l<=r){

        long long Mid=(l+r)/2;

        if(dinic.check(Mid))r=Mid-1,ans=Mid;

        else l=Mid+1;

    }

    printf("%lld\n",ans);

}