题目描述

Farmer John 当选为小镇镇长。他在竞选时承诺为镇上的全部农场建设互联网，现在到了兑现承诺的时候。

FJ 已经为自己的农场接入了一条高速网络线路，希望通过铺设光纤把网络分享给其他所有农场。任意两个农场之间都可以直接铺设光纤，输入给出的矩阵记录了相应的线路长度。网络信号能够经过已经接入的农场继续中转，因此只要最终所有农场处在同一个连通网络中即可，不必在每对农场之间都铺设光纤。

为了控制建设费用，FJ 希望在保证每座农场都能接入网络的前提下，使铺设光纤的总长度最小。请根据完整的距离矩阵求出这个最小值。

输入格式

第一行包含整数 $N$，表示农场数量。

接下来给出一个 $N\times N$ 的整数矩阵，第 $i$ 行第 $j$ 个数表示农场 $i$ 与农场 $j$ 之间直接铺设光纤所需的长度。矩阵对角线为 $0$。输入中的数字只按空白符分隔，不需要依赖物理换行位置。

输出格式

输出一行一个整数，表示把全部农场连接到同一网络所需的最小光纤总长度。

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

28

样例说明 #1

选择长度为 $4,8,16$ 的连接，总长度为 $28$。

3
0 1 10
1 0 2
10 2 0

3

样例说明 #2

先连接前两座农场，再用长度 $2$ 的线路连接第三座，总长度为 $3$。

3
0 5 5
5 0 5
5 5 0

10

样例说明 #3

三条可选连接长度相同，选择任意两条都能得到最优网络。

数据范围与约定

$3\le N\le 100$。任意两座不同农场之间的线路长度均为正整数且不超过 $10^5$，距离矩阵描述同一个无向网络。