这提相当经典啊，这题相当猥琐啊。。。。
无向图中给出N个点，M条边，每个点有当前囤积流量和最大容量，任意两个点之间有距离，首先保证所有的流量都可以被节点吸收（即不超过最大容量），然后将流量跑的最大距离限制到最小。
做法:SAP+二分+Floyd
1.首先预处理出任意两点之间的最短路，二分最大距离mid;
2.将每个节点拆成i*2 i*2+1,i*2+1代表流出的点out[i]，i*2代表流进的点in[i]，前者向后者连一条INF的边。
3.建立超级源s，向每个点in[i],连一条当前囤积流量的边，每个点out[i]向超级汇t连一条最大容量的边。
4.在floyd之后的数组中枚举每两个点之间的最短距离，如果<=mid就建立一条out[i]->in[j]的边
跑最大流，如果满流，下降上界，否则提高下界。
这题做了收获很大，学会了控制初始流量的方法和最后流量全部控制在容量内的方法。
另外就是拆点，分成两个点之后，限制了只要进来的流量就一定囤积在该点，由于这个点本身有初始流量，两个点之间连的那条边可以保证自己的流量也可以不流走。非常精彩的构图^_^
PS:顺便说一下的是：虽然这个图是无向图，但是根据题意，走任意方向互不干扰，所以可以拆成两条有向边。一旦有流量经过这条边，那么流量不会流走，也就说明这个流量必须也只能走这么长的距离，这个锁定技巧很不错，于是就能二分了。。。
int n,m;
int s,t;
int now[maxn];
int cap[maxn];
bint mat[maxn][maxn];
bint tol=0;
void input()
{
tol=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==j)mat[i][j]=0;
else mat[i][j]=INF;
}
for(int i=0;i<n;i++)
{
scanf("%d%d",&now[i],&cap[i]);
tol+=now[i];
}
for(int i=0;i<m;i++)
{
int u,v;
bint w;
scanf("%d%d%lld",&u,&v,&w);
u--;
v--;
if(w<mat[u][v])
mat[u][v]=mat[v][u]=w;
}
}
void floyd()
{
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(mat[i][k]!=INF&&mat[k][j]!=INF)
if(mat[i][k]+mat[k][j]<mat[i][j])
mat[i][j]=mat[i][k]+mat[k][j];
}
}
//in node : i*2;
//out node: i*2+1
//node sum: [0,2*n-1]
//s: 2*n
//t: 2*n+1
//tol:2*n+2
bool check(bint mid)
{
for(int i=0;i<2*n+2;i++)
adj[i]=NULL;
len=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
if(i==j)continue;
if(mat[i][j]!=INF&&mat[i][j]<=mid)
{
insert(i*2+1,j*2,INF);
}
}
for(int i=0;i<n;i++)
{
insert(s,i*2+1,now[i]);
insert(i*2+1,i*2,INF);
}
for(int i=0;i<n;i++)
insert(i*2,t,cap[i]);
if(sap(t+1,s,t)==tol)
return true;
else
return false;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
input();
floyd();
s=2*n;
t=2*n+1;
bint l=0;
bint r=INF;
bint ans=-1;
while(l<=r)
{
bint mid=(l+r)>>1;
if(check(mid)==true)
{
r=mid-1;
ans=mid;
}
else
l=mid+1;
}
printf("%lld\n",ans);
}
return 0;
}