Description

本题评测时间较长，请慎重提交，在Waiting状态中的程序请勿再次提交

给定一张泉州市道路网络的地图。道路网络包含了十字路口和双向道路。道路只在十字路口间交汇，但道路也可能通过隧道和桥梁（地图不是平面图）。每对十字路口间最多只被一条道路连接。每个十字路口 $v$ 都有 $p(v)$ 个警察。当道路 $(u,v)$ 的两端十字路口 $u,v$ 的警察之和至少有 $b(u,v)$ 个时是安全的。但是政府希望更有效地调用警察，因此，政府希望在某些十字路口i减少 $z_i$ 个警察，这时十字路口i还有 $p(i)-z_i$ 个警察，政府希望寻找一种方案，使得任意道路 $(u,v)$ 都有 $p(u)+p(v)=b(u,v)$ 来保障最低限度的安全，并且知道最多和最少需要调用多少警察。

Input Format

从文件bez.in读入数据。

第一行两个正整数$n,m$ ($n \le 500,000$, $m \le 3,000,000$)。表示$n$个十字路口和$m$条边道路。

第二行n个整数，依次表示$p(1),p(2),\cdots,p(n)$ ($0 \le p(i) \le 10^6$)。表示第$i$个十字路口有多少个警察。

下面m行，每行三个整数$u,v,b$ ($1 \le u,v \le n, 0 \le b \le 10^6$)，表示连接$u$和$v$的道路需要$b$个警察。

Output Format

向文件bez.out输出数据。

两个正整数，分别表示调用警察数的最小值和最大值，如果不存在方案就输出NIE。

Sample

样例输入1

3 2
5 10 5
1 2 5
2 3 3

样例输出1

12 15

样例输入2

3 3
1 1 1
1 2 1
1 3 1
3 2 1

样例输出2

NIE