题目描述

POJ 3311

修罗王的猛鲁军团虽然溃败了,但仍有不少猛兽逃窜到了魔法世界的各大城市,城市数 不超过$\red{10}$个,给城市的安全带来极大的隐患,魔法学院为此派出一支特别小分队到各大城 市清扫残余的猛兽.现已知到达各大城市所花费的时间，问到达所有城市清扫(清扫的时间 可以忽略)并返回魔法学院的最少时间是多少?

输入格式

包括多组数据，每组数据第一行为城市$\red{N(1≤}$$\red{N≤}$$\red{10),}$随后的$\red{N+1}$行,每行有$\red{N+1}$ 个数，表示魔法学院(以$\red{0}$表示)到$\red{N}$个城市(以$\red{1}$到$\red{10}$表示)的花费时间。

第$\red{i}$行的第$\red{j}$个的值,表示直接从城市$\red{i}$到城市$\red{j}$的代价。

需要注意的是，直接从城市$\red{i}$到城市$\red{j}$并不一定是最快的,这可能因为限速(比如高速路上突然限速$\red{40)}$、红绿灯,等等,另外,从城市$\red{i}$到城市$\red{j}$ 和从城市$\red{j}$到城市$\red{i}$的花费时间也不一定相同,所有数据以$\red{0}$结束。

输出格式

输出从魔法学院出发到达所有城市并返回所用的最少时间。

样例

输入样例

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0

输出样例

8