题目描述

给出一个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

提示

没有写明提示

题目来源

鸣谢Oimaster