#include #define LL long longusing namespace std;const int maxn = 450;const int INF = 1e9;const LL INF_LL = 1LL<<60;LL Dist[maxn][maxn];int Have[maxn], Can[maxn];int N, M;int Full_Flow;LL Limit;struct Edge{ Edge(){} Edge(int from,int to,int cap,int flow):from(from),to(to),cap(cap),flow(flow){} int from,to,cap,flow;};struct Dinic{ int n,m,s,t; //结点数,边数(包括反向弧),源点与汇点编号 vector edges; //边表 edges[e]和edges[e^1]互为反向弧 vector G[maxn]; //邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; //BFS使用,标记一个节点是否被遍历过 int d[maxn]; //d[i]表从起点s到i点的距离(层次) int cur[maxn]; //cur[i]表当前正访问i节点的第cur[i]条弧 void init(int n,int s,int t) { this->n=n,this->s=s,this->t=t; for(int i=1;i<=n;i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap) { edges.push_back( Edge(from,to,cap,0) ); edges.push_back( Edge(to,from,0,0) ); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis,0,sizeof(vis)); queue Q;//用来保存节点编号的 Q.push(s); d[s]=0; vis[s]=true; while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=0; i e.flow) { vis[e.to]=true; d[e.to] = d[x]+1; Q.push(e.to); } } } return vis[t]; } //a表示从s到x目前为止所有弧的最小残量 //flow表示从x到t的最小残量 int DFS(int x,int a) { //printf("%d %d\n", x, a); if(x==t || a==0)return a; int flow=0,f;//flow用来记录从x到t的最小残量 for(int& i=cur[x]; i 0 ) { e.flow +=f; edges[G[x][i]^1].flow -=f; flow += f; a -= f; if(a==0) break; } } return flow; } int Maxflow() { int flow=0; while(BFS()) { memset(cur,0,sizeof(cur)); flow += DFS(s,INF); } return flow; }}DC;bool OK(LL Upper){ DC.init(2*N+2, 0, 2*N+1); for(int i=1; i<=N; i++){ DC.AddEdge(0, i, Have[i]); DC.AddEdge(i+N, 2*N+1, Can[i]); } for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(Dist[i][j] <= Upper) DC.AddEdge(i, j+N, INF); return (Full_Flow == DC.Maxflow());}int main(void){ while(~scanf("%d %d", &N, &M)){ Full_Flow = 0; Limit = 0; for(int i=1; i<=N; i++){ scanf("%d %d", &Have[i], &Can[i]); Full_Flow += Have[i];///记录所有牛的数量 } for(int i=1; i<=N; i++) for(int j=1; j<=N; j++)///跑 Floyd 前的初始化 if(i==j) Dist[i][j] = 0; else Dist[i][j] = INF_LL; int From, To; LL Cost; for(int i=1; i<=M; i++){ scanf("%d %d %lld", &From, &To, &Cost); Dist[From][To] = Dist[To][From] = min(Dist[From][To], Cost);///有重边,只需记录最小的花费那条边 } for(int k=1; k<=N; k++)///Floyd 算法 for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(Dist[i][k] < INF_LL && Dist[k][j] < INF_LL) Dist[i][j] = min(Dist[i][j], Dist[i][k]+Dist[k][j]); Limit = 0;///再次强调这里的时间是覆盖时间,所以我们找出花费最大的两点互大花费作为二分上界 for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) if(Dist[i][j] < INF_LL) Limit = max(Limit, Dist[i][j]); if(!OK(Limit)) puts("-1");///给出最充裕的时间都无法满流肯定是无解了 else{ LL L = 0, R = Limit, ans; while(L <= R){ ///二分答案 LL mid = L + ((R-L)>>1); if(!OK(mid)) L = mid+1; else ans = mid, R = mid-1; } printf("%lld\n", ans); } } return 0;}