80pts

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define int long long

namespace Dinic {
    struct Node { int to,nxt,dis; }e[1000001];

    int tot=1,s,t,head[4005],vis[4005],cur[4005];

    void add(int x,int y,int k) { e[++tot]=Node{y,head[x],k},head[x]=tot; }

    bool bfs() {
        std::memset(vis,0,sizeof vis);
        std::queue<int> q; q.push(s); vis[s]=1;
        while (!q.empty()) {
            int x=q.front(); q.pop();
            for (int i=head[x];i;i=e[i].nxt) {
                int y=e[i].to; cur[x]=head[x];
                if (e[i].dis and !vis[y]) {
                    vis[y]=vis[x]+1;
                    q.push(y);
                }
            }
        }
        return vis[t];
    }

    int dfs(int x,int flow) {
        if (x==t) return flow;
        int res=0;
        for (int i=cur[x];i and flow;i=e[i].nxt) {
            int y=e[i].to; cur[x]=i;
            if (e[i].dis and vis[y]==vis[x]+1) {
                int k=dfs(y,std::min(e[i].dis,flow));
                e[i].dis-=k,e[i^1].dis+=k,res+=k,flow-=k;
            }
        }
        return res;
    }
}
using namespace Dinic;
using namespace std;
int n,m,cnt,sum;
int S[201],P[201],f[201][201];

bool check(int mid) {
	tot=1;
    memset(head,0,sizeof head);
    for (int i=1;i<=n;i++) {
        add(s,i,S[i]),add(i,s,0);
        add(i+n,t,P[i]),add(t,i+n,0);
    }
    for (int i=1;i<=n;i++) 
        for (int j=1;j<=n;j++)
            if (f[i][j]<=mid and i!=j) add(i,j+n,1e18),add(j+n,i,0);
    int res=0;
    while (bfs()) res+=dfs(s,1e18);
    return res==sum;
}

signed main() {
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++) {
		scanf("%lld%lld",S+i,P+i);
		sum+=S[i];
	}
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++) 
            if (i!=j) f[i][j]=1e18;
	for (int i=1,x,y,k;i<=m;i++) {
		scanf("%lld%lld%lld",&x,&y,&k);
		f[x][y]=min(f[x][y],k),f[y][x]=min(f[y][x],k);
	}
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	int l=0,r=1e17,ans=0; t=2*n+1;
	while (l<=r) {
		int mid=(l+r>>1);
        if (check(mid)) r=mid-1,ans=mid;
        else l=mid+1;
	}
    printf("%lld\n",ans);
    return 0;
}