一天，你来到了巨佬市，接任了这个城市的市长。
巨佬市有 $n$ 个结点，$m$ 条道路，每条道路 $(u,v)$ 的中间有 $w(u,v)$ 个钻石。每个结点 $i$ 有 $p_i$ 个守卫。对于结点 $i$ 的每个守卫，可以看守住每条与 $i$ 直接相连的边上的至多 $1$ 个钻石。
也就是说，对于一条边 $(u,v)$，只有 $p_u+p_v \geq w(u,v)$，这条边的所有钻石才可以被守卫的看守住。为了保证钻石的安全，上一任市长已经安排好守卫，使得对于每条道路 $(u,v)$，都有 $p_u+p_v \geq w(u,v)$，即每一条边的两个端点的守卫数不少于这条边的钻石数。
你成为了巨佬市的市长后，为了减少开支，你希望在钻石安全的前提下减少守卫的数量，使得这个城市的每个钻石都恰好仅被一个守卫盯着。也就是通过减小 $p_i$ 的大小，要使对于每条边 $(u,v)$，都有 $p_u+p_v = w(u,v)$。

调整守卫数是有一些复杂的代价的，现在你只想知道，如果有合法的方案，减少的总守卫数量的最小值和最大值是多少。任何时刻，你均需要满足 $p_i$ 是非负整数。

第一行两个正整数 $n,m$。
第二行 $n$ 个非负整数，第 $i$ 个数表示 $p_i$。
下面 $m$ 行，每行三个整数 $u,v,w$，表示一条道路 $(u,v)$，这条道路有 $w$ 个钻石。

输出仅有一行，包含两个非负整数，分别表示减少的守卫数量的最小值和最大值，如果不存在方案就输出 NIE。

3 2
5 10 5
1 2 5
2 3 3

12 15

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

NIE

10 12
14 20 15 20 18 6 8 9 6 8
1 3 7
2 5 11
2 4 8
3 2 8
6 8 10
6 10 2
7 8 12
7 9 4
7 10 4
8 9 8
8 10 8
9 10 0

85 92