Description

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

Format

Input

第一行两个正整数n,m (n<=500,000, m<=3,000,000)。表示n个十字路口和m条边道路。
第二行n个整数，依次表示p(1),p(2),...,p(n) (0<=p(i)<=10^6)。表示第i个十字路口有多少个警察。
下面m行，每行三个整数u,v,b (1<=u,v<=n, 0<=w<=10^6)，表示连接u和v的道路需要w个警察。

Output

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

Sample 1

Input

3 2
5 10 5
1 2 5
2 3 3

Output

12 15

Sample 2

Input

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

Output

NIE

Limitation

3s, 256MiB for each test case.