Problem B
Minimum Spanning Tree

Given a weighted, undirected graph in an adjecency matrix representation, output the weight of its minimum spanning tree.

Figure 1: Graph

 

Figure 2: MST

Input

Input consists of a series of test cases. ($<5$) The first line of each test case will indicate $N$ ($1<=N<=1000$), the number of vertices in the graph. The next $N$ lines will each contain $N$ integers $W$ ($0<=W<=99$) separated by spaces. These lines comprise the unlabeled Adjecency matrix of the graph where each positive integer $W$ represents an undirected edge between the vertex at that column and row respectively. When $W$ equals zero, there is no edge.You may assume that the graph does not contain loops. That is to say, no vertex connects to itself.

Output

Your output should be a the integer weight of any MST of each test case.

5
0 4 4 6 6
4 0 2 0 0
4 2 0 8 0
6 0 8 0 9
6 0 0 9 0
5
0 4 4 6 7
4 0 2 0 0
4 2 0 8 0
6 0 8 0 9
7 0 0 9 0
0

18
19