给定一张黑手党城的道路网络地图。该网络由路口和连接它们的双向街道组成。街道仅在路口处交叉，但它们可能通过隧道或立交桥。每对路口之间最多由一条街道连接。在每个路口 $v$ 处有一个警察局，驻扎着 $p(v)$ 名警察。如果连接路口 $u$ 和 $v$ 的街道两端警察局的警察总数至少为 $b(u,v)$，则该街道被认为是安全的。最初，对于每一条街道，均满足 $p(u)+p(v) \ge b(u,v)$。

然而，由于持续的危机，市长 Byteasar 颁布了《极简安全法》（MSA），规定：

• 每个警察局必须裁减一定数量（可能为零）的警察（我们用 $z(v)$ 表示在路口 $v$ 处的警察局裁减的警察人数）；
• 裁员后，连接任意两个路口 $u$ 和 $v$ 的每条街道，其两端警察局的警察总数必须恰好等于 $b(u,v)$，即：$p(u)-z(u)+p(v)-z(v)=b(u,v)$。

这些规则并没有唯一确定应该裁减多少名警察。Byteasar 想知道，在符合上述规则的前提下，裁减的警察总数（所有路口 $z$ 值的总和）的最小值和最大值分别是多少。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 500\,000$，$0 \le m \le 3\,000\,000$），分别表示黑手党城的路口数量和街道数量，中间用空格分隔。路口编号从 $1$ 到 $n$。第二行包含 $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}$），中间用空格分隔，分别表示街道两端的路口编号以及该街道两端警察局必须驻扎的警察总数最小值。

在总分占比 $56\%$ 的测试点中，额外满足 $n \le 2\,000$ 且 $m \le 8\,000$。

输出格式

如果 Byteasar 的法令可以执行，你的程序应在标准输出中打印一行，包含两个由空格分隔的整数。这两个数字分别表示为执行该法令而裁减的警察总数的最小值和最大值。

如果无法执行该法令，你的程序应打印一行包含单词 NIE（波兰语，意为“不”）。

样例

输入 1

3 2
5 10 5
1 2 5
2 3 3

输出 1

12 15