Description

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.

Input

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

Output

For each case output one line sum of the connected pair shortest distance.

Sample

Input

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

Output

78
20

Source: moonlight