#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int Min(int a,int b){    return a>b?b:a;}int Map[20][20];int dp[20][1<<11];int n;const int INF=0xfffffff;void floyd(){    for(int k=0;k<n;k++)    for(int i=0;i<n;i++){        for(int j=0;j<n;j++){            if(i==j||j==k||i==k) continue;            Map[i][j]=Min(Map[i][j],Map[i][k]+Map[k][j]);        }    }}int dfs(int x,int state){    int ans=INF;    if(x==0&&state==0) return dp[x][state]=0;    if(~dp[x][state]) return dp[x][state];    for(int i=0;i<n;i++){        int t=state&(1<<i);        if(t&&Map[x][i]!=INF){            ans=Min(ans,dfs(i,state^(1<<i))+Map[x][i]);        }    }    return dp[x][state]=  ans;}int main(){    while(scanf("%d",&n),n){        n++;        memset(dp,-1,sizeof(dp));        memset(Map,0,sizeof(Map));        for(int i=0;i<n;i++)            for(int j=0;j<n;j++)            scanf("%d",&Map[i][j]);        floyd();        cout<<dfs(0,(1<<n)-1)<<endl;    }    return 0;}