题目描述

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

输入格式

第一行一个整数 $n$。接下来给出一个 $n\times n$ 的对称矩阵，第 $i$ 行第 $j$ 列表示连接地点 $i,j$ 的费用，对角线为 $0$。矩阵元素以空白分隔，可能在一行中换行。

输出格式

输出最小的总连接费用。

样例

3
0 1 2
1 0 1
2 1 0

2

数据范围

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