题目描述

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 $100000$。

输入格式

第一行：一个整数 $N$，表示农场的个数（$3 \le N \le 100$）。
接下来的各行包含了一个 $N \times N$ 的矩阵，表示每个农场之间的距离。由于每一行的长度可能超过 $80$ 个字符，矩阵可能会断行。但逻辑上是 $N$ 行，每行 $N$ 个用空格分隔的数。对角线上的元素均为 $0$，表示从第 $i$ 个农场到自身的距离为 $0$。

输出格式

一行一个整数，表示连接所有农场所需光纤的最小总长度。

样例

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

28

数据范围

• $3 \le N \le 100$
• 距离为非负整数，不超过 $100000$
• 图是完全图，保证对称（$d_{ij} = d_{ji}$）