#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using pii=pair<int,int>;
using vlai=valarray<int>;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9

struct ChuLiu_Edmonds{
    #define c first
    #define s second.first
    #define t second.second
    using Edge=pair<int,pair<int,int>>;
    vector<Edge> edge;
    int n;
    ChuLiu_Edmonds(int N):n(N){}
    void add(int C, int S, int T){ edge.eb(C,mp(S,T)); }
    int solve(int start, int v=-1, vector<Edge> edges=vector<Edge>()){   //start..?§??????????????????? v..????????° edges..????????????
        if(v==-1) v=n,edges=edge;
        //????°?????????§????????????????§????
        vector<Edge> minimum(v,mp(INF,mp(0,0)));  //minimum[i]...??????i?????\???????????????????°???????????????±
        for(auto e:edges){
            minimum[e.t]=min(minimum[e.t],e);
        }
        minimum[start]=mp(-1,mp(-1,start)); //?§????????????\??????????????????
        //??§????????°???????????????????????????
        //????????????
        int count=0;
        vi gnum(v);
        vector<bool> isUsed(n,false);   //?????????????????¢?´¢???????????????
        vector<bool> isCycle(n,false);  //????????°??????????????????????????????
        rep(i,v){   //????????????????????????
            if(isUsed[i]) continue; //????????????????????§????????????????????????
            vi loop;
            int pos=i;  //i?????????????????????
            while(pos!=-1 && !isUsed[pos]){    //?????????????????????????????¨??????????????£???????????§??????????????????
                isUsed[pos]=true;   //???????????????????¢??????????
                loop.pb(pos);
                pos=minimum[pos].s; //?????????????????\??????????§????????§????
            }
            if(pos!=-1){ //??????????????¢?´¢????????¢?´¢???????????´????????\??£?????´??????
                //loop???????????????i????????????????????£?????¶????????£???????????§????????±????¨???????????????????
                bool isLoop=false;
                for(auto j:loop){   //??????????????????????????????????????????
                    gnum[j]=count;
                    if(j==pos){ //??????????????????????????¶????????£???????????????
                        isLoop=true;    //????????\??????????????????????????????????§??????????
                        isCycle[count]=true;    //?????????????????????
                    }
                    if(!isLoop){    //????????????????????????????´???§?????????????????°?????????????????????
                        count++;
                    }
                }
                if(isLoop) count++; //??????????????£?????´???????¬???????????????\??°?????????
            }else{  //pos???0?????¨?????????????????????????\???????????????????????????§????????????
                //????????????????????£??????????????????????????\?????°???????????¨??????????????????
                for(auto j:loop){
                    gnum[j]=count++;
                }
            }
        }
        if(count==v){   //??°????????????????????°??¨??????????????§??????????????????????????§????°???¨???????????¨??????????????????
            int ans=1;
            for(auto e:minimum){
                ans+=e.c;   //??°??????????????????????????????????????£?????¨????????????
            }
            return ans;
        }
        int cycle=0;
        rep(i,v) if(i!=start && isCycle[gnum[i]]) cycle+=minimum[i].c;

        vector<Edge> next;
        for(auto e:edges){  //??°??????????????????????????????
            if(gnum[e.s]==gnum[e.t]) continue;  //?§??????¨??????????????????????????????????????????
            if(isCycle[gnum[e.t]]){   //????????????????????????????????????
                next.eb(e.c-minimum[e.t].c, mp(gnum[e.s], gnum[e.t]));  //???????????????????????????????????????????§????
            }else{
                next.eb(e.c, mp(gnum[e.s], gnum[e.t])); //?????????????????????????????????????????????
            }
        }
        return cycle+solve(gnum[start], count, next);
    }
    #undef c
    #undef s
    #undef t
};


int main(){
	int n;
	while(cin>>n,n){
	    ChuLiu_Edmonds ce(n+1);
 		vvi cost(n+1,vi(n+1));
 		rep(i,n)rep(j,n+1)cin>>cost[i+1][j];
		rep(j,n+1){
		    range(i,1,n+1){
		        if(i!=j) ce.add(cost[i][j],j,i);
		    }
		}  
		cout<<ce.solve(0)<<endl;
	}
	return 0;
}

Measured memory_bytes: 3156