Description

肖哥上次从老板们的手中得到了假期。可是现在他休假回来了，老板们给他安排了一个新活——去放奶牛。

肖哥放奶牛的时候发现，奶牛的吃饭是个问题！肖哥每天喂奶牛吃饭要跑很多个牧场，太累了。如今肖哥知道了这些奶牛是被训练过的，只要听见铃声，它们就会去一个特定的牧场。肖哥打算将食物放在一个牧场上然后发出铃声，就可以统一喂奶牛吃饭了，不用跑很多个牧场了。肖哥他知道平时每只奶牛都在各自喜欢的牧场上活动，（一个牧场不一定只有一头牛），只有听见铃声的时候才会去一个牧场上。每只牛行走的速度一样，但却很慢。所以肖哥打算找到一个牧场，可以让所有奶牛行走的距离和最小。

现给出各头牛在的牧场和牧场间的路线（当然，路线是双向的。同时，还可能出现“重边”，毕竟肖哥总会找些小道走，这样就会导致两个牧场之间不只有一条路了）。肖哥想知道所有牛在吃饭时所要行走的最小距离和。

数据保证至少存在一个牧场和所有牛所在的牧场连通

Input Format

第一行输入一个整数T表示有T组数据（1≤T≤3）

第二行: 三个数：奶牛数 P（1≤P≤200），牧场数 N（2≤N≤300），牧场间道路数 M（1≤M≤1000）。

第三行到第 P+1 行: 1 到 P 头奶牛所在的牧场号。

第 N+3 行到第 N + M + 4 行：每行有三个数：相连的牧场A、B（1≤A，B≤N），两牧场间距 D（1≤D≤255）。

Output Format

对于每组测试样例

输出一行，表示所有奶牛行走的最小的距离和。

1
3 4 6
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
1 2 4

8

Source

1816 Online Judge 10.100.0.232