题目描述

有 $n$ 个地点，需要建设一些双向连接，使任意两个地点都能直接或间接通信。给定任意两个地点之间的连接费用，求使全部地点连通的最小总费用。

输入格式

第一行一个整数 $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

数据范围

$3\le n\le100$。非对角线费用为 $1\sim100000$ 的整数。