UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2801. [Poi2012]Minimalist Security

Statistics 下载数据

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)}的最小值和最大值。

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。

Sample Input

For the input data:
3 2
5 10 5
1 2 5
2 3 3
the correct result is:
12 15
whereas for the following input data:
3 3
1 1 1
1 2 1
1 3 1
3 2 1
the correct result is:
NIE

Sample Output

Hint

Source

鸣谢Oimaster