题目描述

刘老师准备把园区内的所有教学楼接入同一个网络，小珅负责统计楼宇之间铺设光纤的长度。

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

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

输入格式

第一行包含整数 $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$，距离矩阵描述同一个无向网络。