该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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练习