#include <iostream>
#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define DEB 0


int d[20];


/*
  Å¬SæLüØ(Chu-Liu/Edmond)Aint^
  ×Úsñ edge[n][n](O[o)
  ¸_rootðªÆµÄ
  ãÍAedgeÌàª«·¦çêéÌÅÓ
  ^ðÏ¦éêÍAmcostÌé¾i»Ì¼ð­µ
  */
typedef int Weight;
const int inf = INT_MAX;
int edge[100][100];
void backward_traverse(int n, int v, int s, int r,
                       vector<int>& no, vector<vector<int> >& comp,
                       vector<int>& prev, vector<Weight>& mcost,
                       vector<int> &mark, int &cost, bool &found){
  if( mark[v] ){
    vector<int> temp = no;
    found = true;
    do{
      cost += mcost[v];
      v = prev[v];
      if( v!=s ){
        while( comp[v].size()>0 ){
          no[comp[v].back()] = s;
          comp[s].push_back(comp[v].back());
          comp[v].pop_back();
        }
      }
    }while(v!=s);

    rep(j,n)if( j!=r && no[j]==s ){
      rep(i,n)if( no[i]!=s && edge[i][j]<inf ){
        edge[i][j] -= mcost[temp[j]];
      }
    }
  }
  mark[v] = true;
  rep(i,n)if( no[i]!=no[v] && prev[no[i]]==v ){
    if( !mark[no[i]] || i==s ){
      backward_traverse(n,i,s,r,no,comp,prev,mcost,mark,cost,found);
    }
  }
}

// root : ¸_root
// n    : m[h
Weight minimum_spanning_arborescence(int root, int n){
  vector<int> no(n);
  vector<vector<int> > comp(n);
  rep(i,n){
    no[i] = i;
    comp[i].push_back(i);
  }
  Weight cost = 0;
  while(1){
    vector<int> prev(n,-1);
    vector<Weight> mcost(n,inf);
    rep(i,n){
      rep(j,n)if( j!=root ){
        if( no[i]!=no[j] && edge[i][j]<inf ){
          if( edge[i][j] < mcost[no[j]] ){
            mcost[no[j]] = edge[i][j];
            prev[no[j]] = no[i];
          }
        }
      }
    }
    bool stop = true;
    vector<int> mark(n);
    rep(i,n){
      if( i==root || mark[i] || comp[i].size()==0 )continue;
      bool found = false;
      backward_traverse(n,i,i,root,no,comp,prev,mcost,mark,cost,found);
      if( found ) stop=false;
    }
    if( stop ){
      rep(i,n)if( prev[i]>=0 ) cost += mcost[i];
      return cost;
    }
  }
  return inf;
}

int main(){
  int n;
  
  while(cin>>n,n){
    rep(i,100)rep(j,100)edge[i][j]=inf;

    /*
    int m; cin>>m;
    rep(i,100)rep(j,100)edge[i][j]=inf;
    rep(i,m){
      int a,b,c; cin>>a>>b>>c;
      edge[a][b] = c;
    }
    rep(i,n){
      rep(j,n){
        printf("%d ",edge[i][j]==inf ? -1 : edge[i][j]);
      }
      puts("");
    }
    cout << minimum_spanning_arborescence(0,3) << endl;
      */
    int tmp_edge[20][20];
    rep(i,n){
      cin>>d[i];
      rep(j,n){
        cin>>edge[j][i];
        edge[j][i] = min(edge[j][i], d[i]);
        tmp_edge[j][i] = edge[j][i];
      }
    }
    
#if DEB
    rep(i,n){
      rep(j,n){
        printf("%3d ",edge[i][j]);
      }
      puts("");
    }
#endif

    Weight ret = inf;
    rep(i,n){
      ret = min(ret,minimum_spanning_arborescence(i,n)+d[i]);
      rep(j,n)rep(k,n)edge[j][k]=tmp_edge[j][k];
    }
    cout << ret << endl;
   
  }
  
  
  return 0;
}

Measured memory_bytes: 0