某乡有 nnn 个村庄，有一个售货员，他要到各个村庄去售货。
任意两个村庄 i，ji，ji，j，村庄 iii 到 jjj 的路程 sijs_{ij}sij 是已知的 (不保证 sij=sjis_{ij}=s_{ji}sij=sji )。
为了提高效率，他从商店出发，经过所有村庄一次且仅一次，然后返回商店所在的村，商店所在的村庄为 1。
现在他想知道他最少要走多少路。
第1行，输入村庄数nnn。
第2到(n+1)(n+1)(n+1)行，每行n个数。第(i+1)(i+1)(i+1)行的第jjj个数为村庄 iii 到村庄 jjj 的路程 sijs_{ij}sij （sii=0s_{ii}=0sii=0 ）
输出一个整数，表示最短的路程。
输入样例 #1
4 0 1 4 5 1 0 8 6 1 10 0 10 4 8 3 0
输出样例 #1
11
2≤n≤152 \le n \le 152≤n≤15
1≤sij≤1001 \le s_{ij} \le 1001≤sij≤100且保证随机
样例解释：
售货员走的路径为1→2→4→3→1 1 \rightarrow 2 \rightarrow 4 \rightarrow 3 \rightarrow 1 1→2→4→3→1 路程为11