题目描述

小镇计划为 $N$ 个村庄修建公路，使得任意两个村庄之间都可以通过公路直达或中转到达。已知每两个村庄之间的距离（非负整数），请设计一种修路方案，使得所有村庄连通且总修路长度最短。

输入格式

第一行为村庄个数 $N$（$3 \leq N \leq 100$）。

接下来是一个 $N \times N$ 的距离矩阵，$N$ 行每行 $N$ 个用空格分隔的整数，第 $i$ 行第 $j$ 列表示村庄 $i$ 到村庄 $j$ 的距离。对角线为 $0$（自己到自己无距离）。

输出格式

一个整数，表示使所有村庄连通的最短总修路长度。

样例

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

28

提示

数据范围

$3 \leq N \leq 100$，每两个村庄间的距离不超过 $10^5$。