Minimum Rope Length

You are given a distance matrix representing the distances between a set of lanterns. Your task is to compute the minimum total rope length required to connect all the lanterns without forming a cycle, which is equivalent to finding the weight of a Minimum Spanning Tree (MST) of a complete graph. A well‐known algorithm to solve this problem is Prim's algorithm. The weight of the MST is given by \( \sum_{e \in T} w(e) \), where \( T \) is the set of edges in the tree and \( w(e) \) represents the weight (or rope length) of edge \( e \).

inputFormat

The input consists of multiple test cases. For each test case:

• The first line contains an integer \( n \) representing the number of lanterns (nodes).
• The next \( n \) lines each contain \( n \) space-separated integers, representing the distance matrix. The \( j^{th} \) number on the \( i^{th} \) line denotes the distance between lantern \( i \) and lantern \( j \).

The input terminates with a test case where \( n = 0 \). This test case should not be processed.

Note: The input should be read from standard input (stdin).

outputFormat

For each test case, output a single line that contains the minimum total rope length required to connect all the lanterns. The output should be written to standard output (stdout).

## sample

3
0 2 3
2 0 1
3 1 0
0

3

</p>