#2801. [Poi2012]Minimalist Security

题目描述

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

输入格式

第一行两个正整数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)。

输出格式

两个正整数，分别表示sum{z(i)}的最小值和最大值，如果不存在方案就输出NIE。

样例

样例输入

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

样例输出

数据范围与提示