#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_INT = 2147483647;
const int INF = 0x3f3f3f3f;
const int MAXN = 200010;
int in(){
	int x = 0,f = 1;
	char c = getchar();
	while (!isdigit(c)){
		if (c == '-'){
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c)){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}
int dis[12][12],dp[1<<11][12];
int n,ans;
signed main(){
	//freopen("xxx.in","r",stdin);
	//freopen("xxx.out","w",stdout);
	while(scanf("%d",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(dis[i][k]+dis[k][j] < dis[i][j]){
						dis[i][j] = dis[i][k]+dis[k][j];
					}
				}
			}
		}
		for(int s = 0;s <= (1<<n)-1;s++){
			for(int i = 0;i <= n;i++){
				if(s&(1<<(i-1))){
					if(s == (1<<(i-1))){
						dp[s][i] = dis[0][i];
					}
					else{
						dp[s][i] = INF;
						for(int j = 0;j <= n;j++){
							if(s & (1<<(j-1)) && j != i){
								dp[s][i] = min(dp[s][i],dp[s^(1<<(i-1))][j]+dis[j][i]);
							}
						}
					}
				}
			}
		}
		ans = dp[(1<<n)-1][1]+dis[1][0];
		for(int i = 2;i <= n;i++){
			if(dp[(1<<n)-1][i]+dis[i][0] < ans){
				ans = dp[(1<<n)-1][i]+dis[i][0];
			}
		}
		cout << ans << endl;
	}
	return 0;
}