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.
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=11In 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
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
