Description

有n个点，用二维矩阵给出任意两个点之间的距离a[i]j，求连接所有点所需要的最小距离和。
以上就是最小生成树的概念。

Format

Input

有多组测试数据。
第一行：N（3≤N≤100）。
下来给出一个N*N的矩阵。a[i][j]表示第i个点和第j个点之间的距离。

Output

输出最小生成树的长度。

Sample 1

Input

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

Output

28

Limitation

1s, 128MB for each test case.

Hint

Source

TYWZ练习