小青鱼正在一张地图上指挥你最喜欢的机器人朋友们。这张地图被表示为一个拥有 $n$ 个节点和 $m$ 条边的连通无向图。节点从 $1$ 到 $n$ 编号，第 $i$ 个节点的权值为 $a_i$。边从 $1$ 到 $m$ 编号，第 $i$ 条边的权值为 $w_i$。

最初，有 $n$ 个机器人，每个节点上各有一个：第 $i$ 个机器人放置在节点 $i$ 上。每天，小青鱼可以进行任意次数的以下操作：

• 选择一个当前位于节点 $u$ 的机器人 $x$，以及一条与 $u$ 相连、权值为 $w$ 的边 $(u, v)$。将该机器人从 $u$ 移动到 $v$。此操作的花费为 $w$ 元。
• 选择两个当前位于同一节点 $u$ 的机器人 $x$ 和 $y$。将它们合并为一个机器人。此操作的花费为 $a_u$ 元。

小青鱼非常想让你开心，但是……好吧，你只喜欢一个机器人。因此，小青鱼必须将所有机器人合并为一个机器人。请帮他求出达成这一目标所需的最小总操作花费！

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$ ($T \ge 1$)，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($n \ge 1$)，分别表示节点数和边数。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$)，表示每个节点的权值。

接下来的 $m$ 行描述所有的边。其中的第 $i$ 行包含三个整数 $u_i$，$v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n$，$1 \le w_i \le 10^9$，$u_i \ne v_i$)，表示一条连接节点 $u_i$ 和 $v_i$ 的边。

保证图是连通的，但可能存在连接同一对节点的重边。

保证所有测试数据的 $n$ 之和不超过 $5 \times 10^5$，所有测试数据的 $m$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示将所有机器人合并为你所喜欢的单个机器人所需的最小总花费。

可以证明，在题目的限制条件下，总是存在一种有效的方案。

样例

输入 1

3
4 4
2 3 7 1
1 2 3
1 3 1
2 3 2
3 4 2
5 4
100000 100000 100000 100000 1
1 2 10
2 3 100
3 4 1000
4 5 10000
1 0
1000000000

输出 1

12
43214
0