Page not loading? Try clicking here.
Placeholder

#10419

Interesting Outing 10s 1024MB

Problems

You are hosting visitors from out of town, and want to take them out and show them the most interesting places in town.

There are \mathbf{N} interesting sights you want to tour. You have identified \mathbf{N}-1 interesting methods of transportation. Each method of transportation bidirectionally connects a pair of sights. Luckily, there is exactly one way to get from any interesting sight to another without using any transportation method more than once.

You know how much it would cost for the group to use each transportation method one time (you pay once per use). You can decide the starting and ending sights of the tour (they can be the same or different sights). You do not need to worry about the cost of getting to the starting point nor coming back from the ending point, only the cost of transportation between sights during the tour. What is the cheapest way to see all sights at least once each?


Input

The first line of the input gives the number of test cases, \mathbf{T}. \mathbf{T} test cases follow. Each test case starts with a line containing a single integer \mathbf{N}, the number of sights you want to tour. Then, \mathbf{N}-1 lines follow. The i-th of these lines contains three integers \mathbf{A_i}, \mathbf{B_i}, and \mathbf{C_i}, representing that the i-th method of transportation can take your group from sight \mathbf{A_i} to sight \mathbf{B_i} or from sight \mathbf{B_i} to sight \mathbf{A_i} for a cost of \mathbf{C_i} coins per usage.


Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is an integer representing the minimum cost of a tour that visits each sight at least once.


Example 

3
6
1 3 10
4 5 10
3 4 10
4 6 20
2 3 30
6
1 3 35
4 5 10
3 4 10
4 6 20
2 3 30
5
1 3 1000000000
2 3 1000000000
3 4 1000000000
3 5 1000000000
Case #1: 100
Case #2: 145
Case #3: 6000000000
In Sample Case #1 (as seen below), an optimal route (marked with a red line in the picture above) goes through the following sights: 2, 3, 1, 3, 4, 5, 4, 6. In Sample Case #2 (as seen above), the only change compared with the setup in Sample Case #1 is that the transportation between sights 1 and 3 got more expensive: from 10 to 35. The route 2, 3, 1, 3, 4, 5, 4, 6 costs 150 in this scenario and it is not optimal. The optimal route is 2, 3, 4, 6, 4, 5, 4, 3, 1 instead (also marked in red in the picture). Notice in Sample Case #3 that the answer may be larger than 2^{32}.

Source

GCJ 2022iow C

You must sign in to write code.