#描述#
Give you a graph of a forest, which contains V (1<=V<=10000) nodes and E ( E < V) edges. As we know, a forest is made up of some trees, which means there is no circle in this graph. Now your task is to calculate the sum of shortest distance between all the pairs which is connected.
The answer will be the same as d12+ d13 + … + d1n + d23 + d24 + … + d2n + d34 +… + dn-1n after you defining the distance of unconnected pairs as 0 and dv1v2 defined as the shortest distance between v1 and v2.

#格式#
##输入格式##
The first line of the input file contains a integer of the case number T(1&lt=T&lt=50). For each case, line one: two numbers V,E. Then following E lines
Every line contain three numbers va vb d(1&lt=va,vb&lt=V,1&ltd&lt100), which means there is a road between node va and vb ,and the length of the road is d.

##输出格式##
For each case output one line sum of the connected pair shortest distance.

#样例1#
##样例输入1##

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

##样例输出1##

78
20

#限制#
1000ms
32768KB

#提示#

#来源#
moonlight