Aurora Saturday 14:30 Python Practice 22.04.16.

22 Apr Aurora Saturday 14:30 Python Practice 22.04.16.

Question:

A provincial government is going to build roads to connect of any two towns in the province(but not necessarily directly connected by road, as long as it can be reached indirectly by road). They have the table lists the distance between any two towns. The goal of the provincial government is trying to minimize the total length of the road to be paved.

Please calculate the minimum total road length.

Input Specification:
Input contains several test cases. The first line of each test case gives the number of towns N ( < 100 ); the next N*(N-1)/2 lines correspond to the distance between towns, and each line gives a pair of positive integers, which are the number of two towns, and the distance between the two towns. For simplicity, towns are numbered from 1 to N.
When N is 0, the input ends.

Output Specification:
For each test case, output the minimum total road length in one line.

Sample Input
3
1 2 1
1 3 2
2 3 4
4
1 2 1
1 3 4
1 4 1
2 3 3
2 4 2
3 4 5
0

Sample Output
3
5