题目描述

某乡有$n$个村庄($1<n \le 20$)，有一只PBC，他要到各个村庄去售货，各村庄之间的路程$s(0<s<1000)$是已知的，且$A$村到$B$村与$B$村到$A$村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为$1$，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。

输入格式

村庄数$n$和各村之间的路程(均是整数)。

输出格式

最短的路程。

样例

3
0 2 1
1 0 2
2 1 0

3

提示

输入解释

$3$ {村庄数}

$0 2 1$ {村庄$1$到各村的路程}

$1 0 2$ {村庄$2$到各村的路程}

$2 1 0$ {村庄$3$到各村的路程}