Interesting Outing

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

There are $N$ interesting sights you want to tour. You have identified $N-1$ interesting methods of transportation. Each method connects a pair of sights in both directions. There is exactly one way to get from any sight to any other without using any transportation method more than once.

You know the cost for the group to use each transportation method one time (you pay once per use). You choose the starting and ending sights, which can be the same or different. You do not count the cost of getting to the starting sight or coming back from the ending sight, only the transportation cost during the tour. What is the cheapest way to see all sights at least once each?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing a single integer $N$, the number of sights. Then, $N-1$ lines follow. The $i$-th of these lines contains three integers $A_i$, $B_i$, and $C_i$, meaning the $i$-th transportation method connects sight $A_i$ and sight $B_i$ in both directions at a cost of $C_i$ coins per usage.

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

$1≤T≤100$.

$1≤A_i<B_i≤N$, for all $i$.

It is possible to travel between any pair of sights using only the given transportation methods. (This and the previous limit imply the sights and transportation methods form an unrooted tree.)

$1≤C_i≤10^9$ for all $i$.

In Sample Case #1 (see the picture), an optimal route, marked with a red line, visits sights $2,3,1,3,4,5,4,6$.

In Sample Case #2, the only change from Sample Case #1 is that the transportation between sights $1$ and $3$ got more expensive, rising from $10$ to $35$. The route $2,3,1,3,4,5,4,6$ now costs $150$ and is not optimal. The optimal route is $2,3,4,6,4,5,4,3,1$ instead, also marked in red in the picture.

In Sample Case #3, note that the answer may be larger than $2^{32}$.