题目描述

小明目前在做一份毕业旅行的规划。

打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。

由于经费有限，希望能够通过合理的路线安排尽可能的省些路上的花销。

给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

​注意​：北京为$1$ 号城市。

输入格式

城市个数 $n$。

城市间的车票价钱$n$ 行 $n$ 列的矩阵$m[n][n]$。

输出格式

输出一个整数，表示最小车费花销。

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

13

数据范围

说明

共4 个城市，城市 1 和城市1 的车费为 0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，以此类推。

假设任意两个城市之间均有单程票可买，且价格均在 1000 元以内，无需考虑极端情况。

$1<n≤20$,包括北京 车票价格均不超过 1000 元。