Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Road Minister Techboy

By hasan169 · Limits 1s, 512 MB

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 11 to nn. 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 TT (1T201 \le T \le 20), denoting the number of test cases. The first line contains a single integer NN (1N10001 \le N \le 1000), representing the number of cities in the country. The next N-1 lines contain 3 integer numbers each xix_i, yiy_i (1xi,yin1 ≤ x_i, y_i ≤ n) and wiw_i (0wi2×;1040 ≤ w_i ≤ 2 \times; 10^4). xix_i and yiy_i are the two ends of a road and xiyix_i \ne y_i and wiw_i is the length of that road.

Output

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

Sample

InputOutput
2
3
1 2 3
2 3 4
3
1 2 3
1 3 3
Case 1: 7
Case 2: 9

Discussion

Statistics


88% Solution Ratio

foyaz05Earliest, Jan '17

AashiqFastest, 0.0s

SeyedTabaLightest, 131 kB

sarthakmannaShortest, 926B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.