Brotherhood在KWAI建立了分部,但由于燕大人杰地灵,不是什么人都能够任意进出的,于是现在一个棘手的问题摆在了Ezio面前:情报的传递。 已知燕大内的Brotherhood一共有 n 个团体,有些团体之间有一些关系,你可以把它们看作一条边,每条边连接了两个 **不同** 的团体,现在一共有 m 条边。 现在前辈 Jumbo 要求 Ezio 将一个情报传递给燕大内的所有团体。已知 Ezio 亲自去向团体i告知情报的代价为 val[i] 。Ezio 当然不想一个一个去找啦,他还有很多任务要完成,于是他发现他可以利用团体之间的关系,让某一个已经被传达过情报的团体去告知另一与之有关系团体。 但是团体内部的人懒癌发作,自然不想白白地去帮 Ezio跑 腿。具体来说,针对关系 (u,v) ,如果 Ezio 想要利用它,应该付出的代价为cost(u,v)。 简而言之: 一个团体得到情报有两种方式: 1.由 Ezio 亲自告知,即代价为 val[i]。 2.由一个与之有关系且已经得到情报的团体以 cost(u,v) 为代价得到情报。 现在 Ezio 想要花费最少的代价让所有团体得到情报,你能帮帮他吗? 输入的第一行表示测试数据组数,满足 数据范围:每组测试用例满足 ,
输入描述:
第一行一个整数t(1 对于每组测试用例:第一行两个用空格隔开的整数n和m(1 接下来一行n个用空格隔开的数,第i个数表示val[i]。接下来m行,每行三个用空格隔开的整数u,v和cost(u,v)(1 = u, v = n, 1 = val[i], cost(u, v) = 20000)。


输出描述:
对于每组测试用例,你的程序需要输出一行一个整数表示询问的答案。
示例1

输入

2
5 8
2 8 5 1 10
1 2 5
1 3 9
3 4 5
2 5 6
3 2 2
1 3 8
5 3 4
4 1 8
5 8
7 2 9 10 3
1 2 8
1 3 6
1 4 4
2 5 3
4 5 2
2 4 9
3 5 3
5 4 2

输出

14
14
加载中...