#include <iostream>
using namespace std;

int D[22][22], NewD[22][22], W[22][22], n;
int Best, X[22];
bool Used[22];

void Copy(int A[22][22], int B[22][22], int n){
 for(int i=0;i<n;i++)
  for(int j=0;j<n;j++)
   A[i][j] = B[i][j];
}

void FloydWarshall(){
 Copy(D,W,n);
 for(int k=0;k<n;k++){
  for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
    if (D[i][j] < D[i][k] + D[k][j])
      NewD[i][j] = D[i][j];
    else
      NewD[i][j] = D[i][k] + D[k][j];
  Copy(D,NewD,n);
 }
}

void getW(){
  for(int i=0;i<n;i++)
   for(int j=0;j<n;j++)
    cin>>W[i][j];
}

void printW(int A[22][22]){
  for(int i=0;i<n;i++){
   for(int j=0;j<n;j++)
    cout<<A[i][j]<<' ';
   cout<<endl;
  }
  cout<<endl;
}

int SumofX(int k){  //sum distances X[i],X[i+1] for i=0..k
  int Sum=0;
  for(int i=0;i<k;i++)
   Sum += D[X[i]][X[i+1]];
  if(k==n-1) Sum += D[X[k]][X[0]];
  return Sum;
}

bool OK(int k, int j, int length){ //has j been used in X[0..k-1]?
  if(Used[j]) return false;
  if(length+D[X[k-1]][j] >=Best) return false;

  return true;
}

void printPath(int m){
  for(int i=0;i<=m;i++) cout<<X[i]<<' ';
}

void shortestPath(int k, int length){ //backtrack
  int Sum;

  for(int i=1;i<n;i++){
    if(OK(k,i,length)){ //if ok to let X[k]=i
      X[k]=i;
      Used[i]=true;
      if(k==n-1) //just placed last visit
      {
       if((Sum=SumofX(n-1)) < Best)
       {
         Best = Sum;
       }
      }
      else
       shortestPath(k+1, length+D[X[k-1]][i]);
      Used[i]=false;     //backtrack
    }
  }

}

int main(){
  cin>>n;
  while(n){
   n++;      //inc n so nodes numbered 0..n-1
   getW();

   FloydWarshall();

   Best = 1000000;
   for(int i=1;i<n;i++) Used[i]=false;
   X[0]=0;   //start at pizzeria
   shortestPath(1,0);

   cout<<Best<<endl;

   cin>>n;
  }
return 0;
}