Shortest Path
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

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 n/2 pairs so that the sum of the length between the n/2 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