#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int inf=(1<<30);

int map[12][12];

int dp[1<<11][12],n;

struct Status{

	int i,j,v;

	Status(){}

	Status(int ii,int jj,int vv){i=ii,j=jj,v=vv;}

}que[(1<<11)*12];

int head,tail;

void slove(){

	while(head<tail){

		Status tmp=que[head++];

		if(tmp.v>dp[tmp.i][tmp.j]) continue;

		for(int j=0;j<=n;j++){

			int st=(1<<j);

			int tst=tmp.i|st;

			if(dp[tst][j]>tmp.v+map[tmp.j][j]){

				dp[tst][j]=tmp.v+map[tmp.j][j];

				que[tail++]=Status(tst,j,dp[tst][j]);

			}

		}

	}

	printf("%d\n",dp[(1<<n+1)-1][0]);

}

int main(){

	while(scanf("%d",&n),n){

		for(int i=0;i<=n;i++){

			for(int j=0;j<=n;j++)

			scanf("%d",&map[i][j]);

		}

		for(int i=0;i<(1<<(n+1));i++){

			for(int j=0;j<=n;j++)

			dp[i][j]=inf;

		}

		dp[1][0]=0;

		head=tail=0;

		que[tail++]=Status(1,0,0);

		slove();

	}

	return 0;

}