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)。

输出描述:

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