59 1 s 128 MB

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

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.

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 |