#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<stack>
using namespace std;
#define MAX 105
typedef long long LL;
const double pi=3.141592653589793;
const int INF=1e9;
const double inf=1e20;
const double eps=1e-6;
int d[15][2500];
int main(){
   int n;
   int dis[15][15];
   while(cin>>n&&n){
	   for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) cin>>dis[i][j];
	   for(int k=0;k<=n;k++){
		   for(int i=0;i<=n;i++){
			   for(int j=0;j<=n;j++){
				   if(i!=k&&k!=j&&i!=j) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//Floyd求出每个点之间的最短路，因为这题可以重复经过某个点
				                                                                     //然后就可以看成不能重复经过的TSP问题了
			   }
		   }
	   }
           for(int s=0;s<(1<<n);s++){//s枚举已经经过的城市的情况
		   for(int i=1;i<=n;i++){
			   if(s&(1<<(i-1))){
				   if(s==(1<<(i-1))) d[i][s]=dis[0][i];//经过情况中只有i城市，所以是从0出发的。
				   else {
					   d[i][s]=INF;
					   for(int j=1;j<=n;j++){
						   if(j!=i&&s&(1<<(j-1))){//枚举已经经过j，并且j不是i
							   d[i][s]=min(d[i][s],dis[j][i]+d[j][s^(1<<(i-1))]);//从j-i的情况，当时经过城市里没有i
						   }
					   }
				   }
			   }
		   }
	   }
	   int ans=INF;
	   for(int i=1;i<=n;i++){
		   ans=min(ans,d[i][(1<<n)-1]+dis[i][0]);
	   }
	   printf("%d\n",ans);
	   
   }
    return 0;
}