编程题：ACM宣传

LB大神想组织集训队去学校各处宣传ACM，但是大神不想让队员们走太多路，因此想写代码计算一下，到各地宣传再回到博知401的最短路径总和是多少。
已知：学校一共有n个宣传点，博知401是标号为1的点。剩下n-1个点每个点各派1位队员，询问每个队员到达宣传点再回到博知401的最短路径和是多少。

### 输入格式:

输入由T个案例组成。输入的第一行只包含正整数T。
接下来是N和M，1 <= N,M <= 1000000，表示N个点和连接N个点的M条边。
然后有M行，每行包括三个值U,V,W，表示从点U到点V需要W的路程。你可以假设该图连通。

### 输出格式:

对于每个案例，打印一行，表示队员们从博知401出发到其他点再回到博知401的路径总和的最小值。

### 输入样例:

in
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50


### 输出样例:

out
46
210







答案：若无答案欢迎评论