#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30

using namespace std;
typedef long long ll;

struct edge {
    int from,to;
    int cost;

    edge(int t,int c) : to(t),cost(c) {}
    edge(int f,int t,int c) : from(f),to(t),cost(c) {}

    bool operator<(const edge &e) const {
        return cost < e.cost;
    }
};

void backward_traverse(int v,int s,int r,vector<edge> gg[],vector<int> &no,vector<vector<int> > &comp,vector<int> &prev,vector<vector<int> > &next,vector<int> &mcost,vector<int> &mark,int &cost,bool &found,int n) {

    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(k,comp[s].size()) {
            int j = comp[s][k];
            if(j != r) {
                rep(l,gg[j].size()) {
                    if(no[gg[j][l].from] != s) {
                        gg[j][l].cost -= mcost[temp[j]];
                    }
                }
            }
        }
    }

    mark[v] = true;
    rep(k,next[v].size()) {
        int i = next[v][k];
        if(no[i] != no[v] && prev[no[i]] == v) {
            if(!mark[no[i]] || i == s) {
                backward_traverse(i,s,r,gg,no,comp,prev,next,mcost,mark,cost,found,n);
            }
        }
    }
}

int minimum_spanning_arborescence(vector<edge> G[],int n,int r) {
    vector<edge> gg[n];

    rep(i,n) {
        rep(j,G[i].size()) {
            edge e = G[i][j];
            gg[e.to].push_back(e);
        }
    }

    vector<int> no(n);
    vector<vector<int> > comp(n);

    rep(i,n) {
        no[i] = i;
        comp[i].push_back(i);
    }

    int cost = 0;
    while(true) {
        vector<int> prev(n,-1);
        vector<int> mcost(n,INF);

        rep(j,n) {
            if(j == r) continue;

            rep(k,gg[j].size()) {
                int i = gg[j][k].from;

                if(no[i] != no[j]) {
                    if(gg[j][k].cost < mcost[no[j]]) {
                        mcost[no[j]] = gg[j][k].cost;
                        prev[no[j]] = no[i];
                    }
                }
            }
        }

        vector<vector<int> > next(n);
        rep(i,n) {
            if(prev[i] >= 0) {
                next[prev[i]].push_back(i);
            }
        }

        bool stop = true;
        vector<int> mark(n);
        rep(i,n) {
            if(i == r || mark[i] || comp[i].size() == 0) continue;
            
            bool found = false;
            backward_traverse(i,i,r,gg,no,comp,prev,next,mcost,mark,cost,found,n);

            if(found) stop = false;
        }

        if(stop) {
            rep(i,n) {
                if(prev[i] >= 0) cost += mcost[i];
            }

            return cost;
        }
    }
}

int main() {
    int n;

    while(cin >> n && n) {
        vector<int> v[30];
        vector<int> pre(n);
        
        rep(i,n) {
            rep(j,n+1) {
                int t;
                cin >> t;
        
                v[i].push_back(t);
            }
        }

        vector<edge> G[n+1];
        REP(i,1,n+1) {
            G[0].push_back(edge(0,i,v[i-1][0]));
        }

        rep(i,n) {
            REP(j,1,n+1) {
                G[j].push_back(edge(j,i+1,v[i][j]));
            }
        }

        cout << minimum_spanning_arborescence(G,n+1,0) << endl;
    }

    return 0;
}

Measured memory_bytes: 1244