时间限制：1秒　　内存限制：256M

---

【问题描述】

　　货郎担问题也叫旅行商问题，即TSP问题（Traveling Salesman Problem），是数学领域中著名问题之一。

　　有 \(n\) 个城市，用 \(1，2，…，n\) 表示，城 \(i,j\) 之间的距离为 \(d_{ij}\)，有一个货郎从城 1 出发到其他城市一次且仅一次，最后回到城市 1，怎样选择行走路线使总路程最短？

【输入格式】

　　村庄数 \(n\) 和各村之间的路程 \(d[i][j]\) （均是整数）。

【输出格式】

　　最短的路程。

【输入输出样例】

　Input

3
0 2 1
1 0 2
2 1 0

　Output

3

【数据说明】

　　对于 \(100\%\) 的数据，\(1<N≤20\)，\(0<d[i][j]<1000\)。

【来源】

　　Mr.he