說明

有一群人到了一個蠻荒之地開墾，經過很多努力，開闢了 $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	無額外限制。