Road Minister Techboy

Techboy is appointed as the minister of roads and highway in his country Better-Not-Name-It. Now he wants to visit all the cities of his country to know more about the current condition of the roads. But as he is a very lazy person he wants to travel as little as possible. He wants to visit all the cities at least once.

All the cities in the country Better-Not-Name-It are numbered from 1 to $n$. Currently, Techboy is in the city numbered 1. He will start his journey from this city and can end in any city of his country, but he will visit all the cities at least once. He wants to travel the minimum possible distance. Now help Techboy find the minimum distance he needs to travel.

Input

Input starts with an integer $T$ ($1 \le T \le 20$), denoting the number of test cases. The first line contains a single integer $N$ ($1 \le N \le 1000$), representing the number of cities in the country. The next $N-1$ lines contain 3 integer numbers each $x_i$, $y_i$ ($1 ≤ x_i, y_i ≤ n$) and $w_i$ ($0 ≤ w_i ≤ 2 \times; 10^4$). $x_i$ and $y_i$ are the two ends of a road and $x_i \ne y_i$ and $w_i$ is the length of that road.

Output

For each test case, print a line $\texttt{Case x: y}$ where $\texttt{x}$ is to be replaced by the test case number and $\texttt{y}$ is to be replaced by the minimum distance Techboy needs to travel.

Sample

Input	Output
2 3 1 2 3 2 3 4 3 1 2 3 1 3 3	Case 1: 7 Case 2: 9