#3141. [Poi2012]Minimalist Security
[Poi2012]Minimalist Security
Description
给出一个N个顶点、M条边的无向图,边(u,v)有权值w(u,v),顶点i也有权值p(i), 并且对于每条边(u,v)都满足p(u)+p(v)>=w(u,v)。 现在要将顶点i的权值减去z(i),其中0<=z(i)<=p(i)。 修改后设顶点i的权值p'(i)=p(i)-z(i),对于每条边(u,v)都满足p'(u)+p'(v)=w(u,v)。 求sum{z(i)}的最小值和最大值。
Format
Input
第一行两个正整数n,m (n<=500,000, m<=3,000,000)。 第二行n个整数,依次表示p(1),p(2),...,p(n) (0<=p(i)<=10^6)。 下面m行,每行三个整数u,v,w (1<=u,v<=n, 0<=w<=10^6),表示存在一条权值为w的边(u,v)。
Output
两个正整数,分别表示sum{z(i)}的最小值和最大值,如果不存在方案就输出NIE。
Samples
3 2
5 10 5
1 2 5
2 3 3
12 15