说明

有一群人到了一个蛮荒之地开垦，经过很多努力，开辟了 $m$ 个农场，他们也开辟了一些道路连接这些农场，每一条道路连接两个不同的农场。由于道路开辟困难，总共只开辟了 $m-1$ 条道路，但任何两个农场之间，都有长度大于零的路径直接或间接连接。王老先生拥有其中的 $n$ 个农场，不过这些农场不一定全部直接连接在一起，可能有两个王老先生的农场之间，需要经过其他人的农场才能互相来回。

王老先生将他的农场由 $1$ 到 $n$ 编号，其中 $1$ 号农场也是他的住家。他记录了他的任两个农场之间的距离，想要规划出一条从住家（$1$ 号农场）出发、巡视经过所有他的农场、最后回到住家的最短路径。当然，对于规划出的路径，各个农场经过的顺序与次数皆不限定，中间也可以经过其他人的农场。注意到王老先生并没有其他农场的信息，因此王老先生只能通过这 $n$ 个农场两两之间的距离来计算最短路径。

请你撰写一个程序，帮王老先生计算出最短的路径长度，满足该路径能巡视经过所有他的农场，最后回到住家。

举例来说，假设 $m=5$，而王老先生拥有其中的 $n=4$ 个农场。下图表示了所有 $m$ 个农场的结构，其中王老先生的农场被标上了 $1\sim 4$ 的编号：

:::align{center} :::

由于王老先生记录了他的任两个农场之间的距离，我们可以将这些距离表示成如下的距离矩阵 $d$，其中 $d_{i, j}$（第 $i$ 列的第 $j$ 行）是农场 $i$ 到 $j$ 的距离。可以发现，一个距离矩阵必然是对称矩阵且对角线均为 $0$：

$$\begin{array}{|c|c|c|c|} \hline 0 & 4 & 8 & 10\\ \hline 4 & 0 & 6 & 8\\ \hline 8 & 6 & 0 & 2\\ \hline 10 & 8 & 2 & 0\\ \hline \end{array}$$

而通过距离矩阵提供给我们的信息，可以找出在这个例子中，最短的路径是 $1 \to 3 \to 4 \to 2 \to 1$，长度为 $8+2+8+4=22$。

输入格式

$$\begin{aligned} &n \\ &d_{1,1} \; d_{1,2} \; d_{1,3} \; \cdots \; d_{1,n} \\ &d_{2,1} \; d_{2,2} \; d_{2,3} \; \cdots \; d_{2,n} \\ &d_{3,1} \; d_{3,2} \; d_{3,3} \; \cdots \; d_{3,n} \\ &\vdots \\ &d_{n,1} \; d_{n,2} \; d_{n,3} \; \cdots \; d_{n,n} \end{aligned}$$

• $n$ 代表王老先生拥有的农场个数。
• $d_{i,j}$ 代表农场 $i$ 到 $j$ 的距离。
• 题目叙述中提到的 $m$ 并不会出现在输入中。

输出格式

$$D$$

• $D$ 为一正整数，代表王老先生从 $1$ 号农场出发、巡视经过所有他的农场、最后回到 $1$ 号农场的最短路径长度。

3
0 2 4
2 0 2
4 2 0

8

4
0 4 8 10
4 0 6 8
8 6 0 2
10 8 2 0

22

提示

数据限制

• $2 \leq n\leq 5000$。
• $0\leq d_{i,j}\leq 10^8$。
• 若 $i\neq j$，则 $d_{i, j}> 0$。
• 若 $i = j$，则 $d_{i, j} = 0$。
• 对于所有 $i, j$，$d_{i, j} = d_{j, i}$。
• 保证存在一个正整数 $m\geq n$，满足存在一个 $m$ 点 $m-1$ 条边、每条边长度都大于零的连通图，满足 $d_{i, j}$ 为在其上取 $n$ 个点后的距离矩阵。
• 输入的数字皆为整数。

评分说明

本题共有六组子任务，条件限制如下所示。每一组可有一或多笔测试数据，该组所有测试数据皆需答对才会获得该组分数。

子任务	分数	额外输入限制
1	7	$n=3$。
2	12	$n\leq 20$。
3	13	$n\leq 200$ 且 $m=n$，也就是所有的农场都是王老先生的。
4	21	$m=n$，也就是所有的农场都是王老先生的。
5	23	$n\leq 1000$。
6	24	无额外限制。