#P18379. Bot Friends 2
Bot Friends 2
Bot Friends 2
题目描述
小青鱼正在一张地图上指挥你最喜欢的机器人伙伴。地图是一张有 个顶点、 条边的连通无向图。顶点编号为 到 ,其中顶点 的权值为 。边编号为 到 ,其中边 的权值为 。
最初,一共有 只机器人,每个顶点上恰有一只:第 只机器人位于顶点 。
每天,小青鱼可以执行任意次下述操作:
- 选择一只当前位于顶点 的机器人 ,以及一条与 相邻、权值为 的边 。沿这条边将机器人从 移动到 ,花费 元。
- 选择两只当前位于同一个顶点 的机器人 ,将它们合并为一只机器人,花费 元。
小青鱼很想让你开心,但是你只喜欢一只机器人。因此,他必须把所有机器人合并成一只。请你求出,完成这个目标所需的最小操作总费用。
输入格式
输入包含多组测试数据。第一行包含一个整数 (),表示测试数据组数。
对于每组测试数据:
第一行包含两个整数 (),分别表示顶点数和边数。
第二行包含 个整数 ,满足 ,表示各顶点的权值。
接下来 行描述各条边。第 行包含三个整数 ,满足
$$1\le u_i,v_i\le n,\qquad u_i\ne v_i,\qquad 1\le w_i\le10^9,$$表示顶点 与 之间有一条权值为 的无向边。
保证图连通。同一对顶点之间可能有多条边,但不存在自环。
保证同一个输入文件中,所有测试数据的 之和不超过 , 之和不超过 。
输出格式
对于每组测试数据,输出一行,包含一个整数,表示将所有机器人合并成一只所需的最小操作总费用。
可以证明,在本题的条件下一定存在合法方案。
样例输入
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