题目描述

译自 POI 2012 Stage 3. Day 2「Bezpieczeństwo minimalistyczne」

给定一张无向图，点有点权 $p(v)$，边有边权 $b(u,v)$，初始时保证对每条边有

$$p(u) + p(v) \ge b(u,v).$$

现在需要减少一部分点的点权，使得对每条边都恰有

$$p(u) + p(v) = b(u,v).$$

求整张图减少的点权和的最小值和最大值。

---

输入格式

第一行两个整数 $n$ 和 $m$（$1 \le n \le 500\,000$，$0 \le m \le 3\,000\,000$），表示图的点数和边数。

接下来一行 $n$ 个非负整数 $p_1, p_2, \ldots, p_n$（$0 \le p_i \le 10^6$），表示点权。

接下来 $m$ 行，每行三个整数 $u_i, v_i, b(u_i, v_i)$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$，$0 \le b(u_i, v_i) \le 10^6$），表示边和边权。

---

输出格式

如果存在符合条件的方案，输出一行两个整数，表示整张图减少的点权和的最小值和最大值。

如果不存在，输出 NIE。

---

样例 1

输入

3 2
5 10 5
1 2 5
2 3 3

输出

12 15

---

样例 2

输入

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

输出

NIE

---

数据范围与提示

• 对于 $56\%$ 的数据，$n \le 2000$，$m \le 8000$。
• 对于所有数据，$1 \le n \le 500\,000$，$0 \le m \le 3\,000\,000$。