Today HH becomes a designer, and he faces a problem so he asks you for help. Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities. HH the designer is going to design a plan to divide n city into n2 pairs so that the sum of the length between the n2 pairs city is minimum. Now HH has finished it but he doesn't know whether it's true so he ask you to calculate it together. It's guaranteed that n is even.
输入描述:
The first line contains an positive integer T(1≤T≤100), represents there are T test cases.  For each test case: The first line contains an positive integer n(1≤n≤104), represents the number of cities in Treeisland, it's guarantee that n is even.  Then n−1 lines followed. Each line contains three positive integer u, v and len, (u≠v,1≤u≤n,1≤v≤n,1≤len≤109)indicating there is a road of length len between u and v.  It's guarantee you can get to any city from any city.


输出描述:
For each test case, output in one line an integer, represent the minimum sum of length.
示例1

输入

2
4
1 2 5
2 3 8
3 4 6
6
1 3 5
3 2 3
4 5 4
4 3 9
4 6 10

输出

11
31

说明

	In the first example, you can divide them into (1,2), and (3,4), then the minimum sum of length is 5+6=11
	In the second example, you can divide them into (1,3),(2,4),(5,6), hen the minimum sum of length is 5+(3+9)+(10+4)=31
	 
加载中...