题目描述

某乡有 $n$ 个村庄，有一个售货员要到各个村庄去售货。各村庄之间的路程 $s_{i,j}$ 是已知的，并且从 $i$ 村到 $j$ 村和从 $j$ 村到 $i$ 村的路程大多不同。

为了提高效率，他从商店出发，每个村庄恰好去一次，然后返回商店所在的村庄。商店在 $1$ 号村庄。请帮他选一条总路程最短的路线。

输入格式

第一行一个整数 $n$，表示村庄数。

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数表示 $i$ 到 $j$ 的单向路程 $s_{i,j}$（$s_{i,i}=0$）。

输出格式

一行一个整数，表示最短的总路程。

样例

3
0 2 1
1 0 2
2 1 0

3

数据范围与提示

对于全部数据，$2\le n\le 20$，$1\le s_{i,j}<1000$（$i\ne j$）。