Jack农场主的奶牛实在是太讨厌被淋湿了。奶牛们决定在农场设置降雨警报，这样在快要下
雨的时候可以让奶牛们都知道。他们设置设计了一个下雨撤退计划，这样在下雨之前每头奶牛都
能躲到避雨点。然而，天气预报并不总是准确的。为了使得错误的天气预报影响尽可能小，他们
希望尽可能晚地拉响警报，只要保证留有足够的时间让所有的奶牛都能回到避雨点就可以了。
农场有F块草地，1≤F≤200，奶牛们在草地上吃草。这些草地之间有P条路相连，1≤P≤
1500，这些路足够宽，再多的奶牛也能同时在路上行走。
有些草地上有避雨点，奶牛们可以在此避雨。避雨点的容量是有限的，所以一个避雨点不可
能容纳下所有的奶牛。草地与路相比很小，奶牛们通过时不需要花费时间。
计算警报至少需要提前多少时间拉响，以保证所有的奶牛都能到达一个避雨点
// 这题要将每个点拆成2个点 成为二分图 不然可能出现回路
// 然后就和 poj2112一样 二分法求最大最小值
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define maxn 420
#define maxm 108010
#define LL long long
struct Eg{
int to;
int next;
int f;
}E[maxm];
int V[maxn],num;
int N,P;
const long long INF = 1000000000000000LL;
//LL cap[maxn][maxn],flow[maxn][maxn];
LL nu[maxn],c[maxn];
LL dis[maxn][maxn];//,bl[1100];
LL in,out;
void add(int u,int v,int c){
E[num].to=v;
E[num].f=c;
E[num].next=V[u];
V[u]=num++;
E[num].to=u;
E[num].f=0;
E[num].next=V[v];
V[v]=num++;
}
void build(LL max_min){
int i,j;
num=0;
memset(V,-1,sizeof(V));
// memset(flow,0,sizeof(flow));
for(i=1;i<=N;i++) add(0,i,nu[i]);//cap[0][i]=nu[i];
for(i=1;i<=N;i++) add(i+N,N<<1|1,c[i]);//cap[i+N][N<<1|1]=c[i];
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(dis[i][j]<=max_min)
add(i,j+N,MOD);//cap[i][j+N]=INF;
}
int level[maxn];
bool BFS(int s,int t){
memset(level,0,sizeof(level));
queue<int> Q;
int u,v,e;
Q.push(s);
level[s]=1;
while(!Q.empty()){
u=Q.front();
Q.pop();
if(u==t) return true;
for(e=V[u];e!=-1;e=E[e].next){
v=E[e].to;
if(!level[v]&&E[e].f>0)
{
level[v]=level[u]+1;
Q.push(v);
}
}
}
return false;
}
int cur[maxn];
int dfs(int u,int maxf,int t){
if(u==t||maxf==0) return maxf;
int ret=0,f,e,v;
for(e=cur[u];e!=-1;e=E[e].next){// 当前弧优化
v=E[e].to;
if(E[e].f>0&&level[u]+1==level[v]){
f= dfs(v,min(maxf,E[e].f),t);
E[e].f-=f;
E[e^1].f+=f;
maxf-=f;
ret+=f;
cur[u]=e;
if(maxf==0) break;
}
}
return ret;
}
int Dinic(int s,int t){
int flow=0;
while(BFS(s,t)){
for(int i=0;i<=t;i++)
cur[i]=V[i];
flow+=dfs(s,MOD,t);
}
return flow;
}
int main(){
int i,j,k;
while(scanf("%d %d",&N,&P)!=EOF){
in=out=0;
for(i=1;i<=N;i++){
scanf("%lld %lld",&nu[i],&c[i]);
in+=nu[i];
out+=c[i];
}
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(i!=j)
dis[i][j]=INF;
else dis[i][j]=0;
while(P--){
scanf("%d %d %d",&i,&j,&k);
LL temp=k;
dis[i][j]=dis[j][i]=min(dis[i][j],temp);
}
if(out<in) { printf("-1
");continue;}
LL L=0,R=0,mid;
for(k=1;k<=N;k++)
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
if(dis[i][j]<INF) R=max(R,dis[i][j]);
}
int tp;
build(R);
tp=Dinic(0,N<<1|1);
if(tp<in) { printf("-1
");continue;}
while(L<R){
mid=(L+R)>>1;
build(mid);
tp=Dinic(0,N<<1|1);
if(tp>=in) R=mid;
else L=mid+1;
}
printf("%lld
",R);
}
return 0;
}
// 下面是邻接矩阵实现的 速度要慢些
/*
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
using namespace std;
#define MOD 1000000007
#define maxn 420
#define maxm 48010
#define LL long long
int N,P;
const long long INF = 1000000000000000LL;
LL cap[maxn][maxn],flow[maxn][maxn];
LL nu[maxn],c[maxn];
LL dis[maxn][maxn];//,bl[1100];
LL in,out;
void build(LL max_min){
int i,j;
memset(cap,0,sizeof(cap));
memset(flow,0,sizeof(flow));
for(i=1;i<=N;i++) cap[0][i]=nu[i];
for(i=1;i<=N;i++) cap[i+N][N<<1|1]=c[i];
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(dis[i][j]<=max_min)
cap[i][j+N]=INF;
}
int level[maxn];
bool BFS(int s,int t){
memset(level,0,sizeof(level));
queue<int> Q;
int u;
int i;
Q.push(s);
level[s]=1;
while(!Q.empty()){
u=Q.front();
Q.pop();
if(u==t) return true;
for(i=1;i<=t;i++)
if(!level[i]&&cap[u][i]>flow[u][i])
{
level[i]=level[u]+1;
Q.push(i);
}
}
return false;
}
int cur[maxn];
LL dfs(int u,LL maxf,int t){
// printf("%d %d ",u,cur[u]);getch();
if(u==t||maxf==0) return maxf;
LL ret=0,f,i;
for(i=cur[u];i<=t;i++)
if(cap[u][i]>flow[u][i]&&level[u]+1==level[i]){
f= dfs(i,min(maxf,cap[u][i]-flow[u][i]),t);
flow[u][i]+=f;
flow[i][u]-=f;
maxf-=f;
ret+=f;
cur[u]=i;
if(maxf==0) break;
}
return ret;
}
LL Dinic(int s,int t){
LL flow=0;
while(BFS(s,t)){
for(int i=0;i<=t;i++)
cur[i]=1;
flow+=dfs(s,INF,t);
}
return flow;
}
int main(){
int i,j,k;
while(scanf("%d %d",&N,&P)!=EOF){
in=out=0;
for(i=1;i<=N;i++){
scanf("%lld %lld",&nu[i],&c[i]);
in+=nu[i];
out+=c[i];
}
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(i!=j)
dis[i][j]=INF;
else dis[i][j]=0;
while(P--){
scanf("%d %d %d",&i,&j,&k);
LL temp=k;
dis[i][j]=dis[j][i]=min(dis[i][j],temp);
}
if(out<in) { printf("-1
");continue;}
LL L=0,R=0,mid;
for(k=1;k<=N;k++)
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
{
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
if(dis[i][j]<INF) R=max(R,dis[i][j]);
}
int tp;
build(R);
tp=Dinic(0,N<<1|1);
if(tp<in) { printf("-1
");continue;}
while(L<R){
mid=(L+R)>>1;
build(mid);
tp=Dinic(0,N<<1|1);
if(tp>=in) R=mid;
else L=mid+1;
}
printf("%lld
",R);
}
return 0;
}
*/