芭比兰的混乱

时间限制：2 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

众所周知，芭比兰是一个完美的场所，一切都很理想，所有人都做着他们的创造者——美泰公司——所设想的事情。但刻板芭比的肯尼缺少与她的交流，因此他决定分析芭比兰所有居民之间的社交关系图，以了解为何他如此孤独。尽管这并没有帮助他，我们仍来描述他发现的几个事实。

芭比兰共有 $n$ 名居民，其中有 $m$ 对互相交流的人。每位居民 $v$ 有一个 _社会地位_ 指标 $p_v$，而每一对交流的居民 $(u, v)$ 有一个 _亲密程度_ 指标 $d_{u,v}$。那么居民 $v$ 的 _不满意度_ 计算为：

$$ s_v = \sum\limits_{(u, v)} p_v \oplus d_{u,v}, $$

其中 $\oplus$ 表示 异或 运算（按位异或）。所有居民的总不满意度是所有居民的不满意度之和。

在肯尼和芭比多次往返于芭比兰和现实世界之后，如我们所知，整个芭比兰陷入了混乱：几次政权更迭，许多对朋友反目，而这仅仅是冰山一角！在一切恢复平静之前，为了避免新的问题，决定暂时禁止某些居民之间的交流，即从社交图中删除一些边。但是社交图必须保持连通，以避免社会分裂成多个独立群体。

这时，肯尼先前收集的信息就派上用场了！请确定通过删除社交图中的一些边（交流关系），同时使得任意两名居民之间仍然存在一条交流链，所能达到的最小总不满意度是多少。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— 居民数量以及交流过的对数（$1 \le n, m \le 2 \cdot 10^5$）。

第二行包含 $n$ 个整数 $p_i$ —— 每位居民的社会地位（$0 \le p_i \le 10^9$）。

接下来的 $m$ 行每行描述一条边，每行包含三个整数 $v_i, u_i, d_{u_i, v_i}$，表示居民 $u_i$ 和 $v_i$ 之间以亲密程度 $d_{u_i, v_i}$ 交流（$1 \le u_i, v_i \le n$；$0 \le d_{u_i, v_i} \le 10^9$）。

保证对于所有 $i$ 有 $u_i \ne v_i$，且图是连通的。允许多重边。

输出格式

输出一个整数 —— 在删除一些边并保持图连通的情况下，所能达到的最小可能总不满意度。

示例

示例 1

输入

4 5
1 1 4 1
1 2 2
1 3 2
1 4 3
2 3 5
3 4 2

输出

15

示例 2

输入

3 3
1 4 16
1 2 17
2 3 17
1 3 17

输出

39

注

在第二个示例中，最优选择是保留边 $1 \leftrightarrow 3$ 和 $2 \leftrightarrow 3$。那么第一位居民的不满意度为 $1 \oplus 17 = 16$，第二位为 $4 \oplus 17 = 21$，第三位为两次 $16 \oplus 17 = 1$（因为所有边的权值相等）。总和为 $39$。