#1100 Finding a MST

59  1 s   128 MB  

Description

Given a graph, you must find a minimum spanning tree for the graph.

Input

The input includes several cases. For each case, the first line contains the number of vertex, $N (3 \leq N \leq 100)$. The following lines contain the $N$ x $N$ conectivity matrix, where each element shows the weight fo edge from on vertex to another. Logically, they are $N$ lines of $N$ space-separated integers. Physically, they are limited in length to $80$ characters, so some lines continue onto others. Of course, the diagonal will be $0$, since the distance from vertex $i$ to itself is not interesting for this problem.

Output

For each test case, print sum of weights for MST.

Sample Input

Sample Output

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
2
0 1
1 0
28
1