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

包括多组数据，每组数据第一行为城市N(1≤N≤10)，随后的N+1行，每行有N+1个数，表示魔法学院（以0表示）到N个城市（以1到10表示）的花费时间。第i行的第j个的值，表示直接从城市i到城市j的代价。需要注意的是，直接从城市i到城市j并不一定是最快的，这可能因为限速（比如高速路上突然限速40），比如红绿灯等等，另外，从城市i到城市j和从城市j到城市i的花费时间也不一定相同，所有数据以0结束。

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

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

8