#P18379. Bot Friends 2

Bot Friends 2

Bot Friends 2

题目描述

小青鱼正在一张地图上指挥你最喜欢的机器人伙伴。地图是一张有 nn 个顶点、mm 条边的连通无向图。顶点编号为 11 到 nn,其中顶点 ii 的权值为 aia_i。边编号为 11 到 mm,其中边 ii 的权值为 wiw_i。

最初,一共有 nn 只机器人,每个顶点上恰有一只:第 ii 只机器人位于顶点 ii。

每天,小青鱼可以执行任意次下述操作:

  • 选择一只当前位于顶点 uu 的机器人 xx,以及一条与 uu 相邻、权值为 ww 的边 (u,v)(u,v)。沿这条边将机器人从 uu 移动到 vv,花费 ww 元。
  • 选择两只当前位于同一个顶点 uu 的机器人 x,yx,y,将它们合并为一只机器人,花费 aua_u 元。

小青鱼很想让你开心,但是你只喜欢一只机器人。因此,他必须把所有机器人合并成一只。请你求出,完成这个目标所需的最小操作总费用。

输入格式

输入包含多组测试数据。第一行包含一个整数 TT(T≥1T\ge1),表示测试数据组数。

对于每组测试数据:

第一行包含两个整数 n,mn,m(n≥1n\ge1),分别表示顶点数和边数。

第二行包含 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,满足 1≤ai≤10121\le a_i\le10^{12},表示各顶点的权值。

接下来 mm 行描述各条边。第 ii 行包含三个整数 ui,vi,wiu_i,v_i,w_i,满足

$$1\le u_i,v_i\le n,\qquad u_i\ne v_i,\qquad 1\le w_i\le10^9,$$

表示顶点 uiu_i 与 viv_i 之间有一条权值为 wiw_i 的无向边。

保证图连通。同一对顶点之间可能有多条边,但不存在自环。

保证同一个输入文件中,所有测试数据的 nn 之和不超过 5×1055\times10^5,mm 之和不超过 10610^6。

输出格式

对于每组测试数据,输出一行,包含一个整数,表示将所有机器人合并成一只所需的最小操作总费用。

可以证明,在本题的条件下一定存在合法方案。

样例输入

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

样例输出

12
43214
0