Migrated from Lutece 3212 救援行动

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

M 市不幸发生了一场灾难，洪水席卷了该市，只有 $n$ 个大楼的楼顶没有被水淹没。幸运的是，没有人员伤亡。

现在急救队来到了某一个大楼的楼顶，他们需要尽快在楼顶之间建立通道。为了提高效率，急救队需要建立最少的通道使得两两大楼之间存在一条通路。

现在给出两两大楼之间建立通道的花费 $w_{i, j}$。你可以算算他们至少需要花费来建立通道吗？

Input

第一行一个整数 $n$。

接下来 $n$ 行，每行 $n$ 个整数，代表第 $i$ 个大楼和第 $j$ 个大楼之间建立通道的花费（题目数据保证 $w_{i, j} = w_{j, i}$）。

Output

输出一个整数，代表最小花费

Samples

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

28

Constraints

$3\le n\le 100$

$w_{i, j} \le 10^5$

Resources

2024 UESTC ICPC Training for Graph