I came, I saw, I conquered！—Caesar
Casar带着他的军队来到了一个叫作Gallia的国家！Gallia是由N个城市组成，部分之间有通道（双向）！欲想征服这个国家，必须占领所有城市(N个)！战争，必会带来损伤！求征服Gallia的最小的代价！
有两种行为可以执行：
1.可以选个任意城市i，从空中投放士兵占领，代价为fly[i]；
2.在已经占领的城市u向周围扩张! 若u与v有路相连，可付出road(u,v)代价,占领据点v！（此时不用付出代价fly[i]）

先输入一个T（0<T≤20）,表示下面有T组测试数据，每组测试数据第一行包含2个整数：据点数N（1≤N≤10000），通道数(0≤M≤100000)；接下来有M+1行。第一行有N个数：第i个数fly[i],为占领第i个据点的代价；后M行，每行代表一条通道包含3个整数：a,b,c（1≤a≤N, 1≤b≤N,1≤c≤100000） 表示据点a与据点b之间有通道相连，通过所需代价为c！(注意：可能出现重边)

对于每组测试数据，输出包括一行，征服Gallia的最小的代价！形式如下面样例所示。

The 12th ZJNU Anniversary Contest