#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>
#include<queue>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

bool cycle_detection(const vector<vector<int>> &G, vector<bool> &used, vector<bool> &used2, deque<int> &C, int cur){
	used[cur] = true;
	used2[cur] = true;
	
	C.push_back(cur);
	
	for(int nex : G[cur]){
		if(used[nex]){
			if(used2[nex]) {
				while(C.front() != nex){
					C.pop_front();
				}
				return true;
			} else {
				continue;
			}
		}
		
		if(cycle_detection(G, used, used2, C, nex)) return true;
	}
	
	C.pop_back();
	
	used2[cur] = false;
	
	return false;
}

deque<int> cycle_detection(const vector<vector<int>> &G){
	int N = G.size();
	vector<bool> used(N), used2(N);
	deque<int> C;
	
	for(int i = 0; i < N; i++){
		if(used[i] == true) continue;
		C.clear();
		if(cycle_detection(G, used, used2, C, i)) return C;
	}
	
	return {};
}

vector<vector<int>> Chu_Liu_Edmonds(vector<vector<pair<int,int>>> &G, int r, int &cost){
	int N = G.size();
	int tcost = 0;
	
	vector<vector<pair<int,int>>> R(N), NG;
	vector<vector<int>> T(N), NT;
	deque<int> C;
	vector<bool> c(N);
	vector<int> num(N), rnum(N);

	
	int nc;
	
	for(int i = 0; i < G.size(); i++){
		for(int j = 0; j < G[i].size(); j++){
			R[G[i][j].first].push_back({G[i][j].second, i});
		}
	}
	
	
	for(int i = 0; i < N; i++){
		sort(R[i].begin(), R[i].end());
		
		if(i == r) continue;
		
		if(R[i].size() == 0) {
			return {};
		}
		
		tcost += R[i][0].first;
		T[R[i][0].second].push_back(i);
	}
	
	
	C = cycle_detection(T);
	
	if(C.size() == 0){
		cost = tcost;
		return T;
	}
	
	for(int i = 0; i < C.size(); i++){
		c[C[i]] = true;
	}
	
	for(int i = 0, n = 0; i < N; i++){
		if(c[i] == true) {
			rnum[i] = -1;
			continue;
		}
		num[n] = i;
		rnum[i] = n;
		n++;
		
	}
	
	nc = N - C.size();
	
	NG.resize(nc+1);
	
	for(int i = 0, n = 0; i < N; i++){
		if(c[i] == true) {
			for(int j = 0; j < G[i].size(); j++){
				if(c[G[i][j].first] == false) {
					NG[nc].push_back({rnum[G[i][j].first], G[i][j].second});
				}
			}
			
		} else {
			for(int j = 0; j < G[i].size(); j++){
				if(c[G[i][j].first] == true) {
					NG[rnum[i]].push_back({nc, G[i][j].second - R[G[i][j].first][0].first});
				} else {
					NG[rnum[i]].push_back({rnum[G[i][j].first], G[i][j].second});
				}
			}
		}
	}
	
	NT = Chu_Liu_Edmonds(NG, rnum[r], cost);
	
	if(NT.size() == 0) return {};
	
	T.clear();
	T.resize(N);
	
	pair<int,int> e = {0,INF};
	
	
	for(int i = 0; i + 1 < NT.size(); i++){
		for(int j = 0; j < NT[i].size(); j++) {
			if(NT[i][j] == nc) {
				int fuga = 0;
				
				for(int k = 0; k < G[num[i]].size(); k++) {
					if(c[G[num[i]][k].first] == false) continue;
					
					
					if(G[num[i]][k].second - R[G[num[i]][k].first][0].first < e.second) {
						e.first = G[num[i]][k].first;
						e.second = G[num[i]][k].second - R[G[num[i]][k].first][0].first;
						fuga = R[G[num[i]][k].first][0].first;
					}
				}
				T[num[i]].push_back(e.first);
				
				cost += fuga;
				
			} else {
				T[num[i]].push_back(num[NT[i][j]]);
			}
		}
	}
	
	for(int i = 0; i < NT[nc].size(); i++){
		for(int j = 0; j < R[num[NT[nc][i]]].size(); j++){
			if(c[R[num[NT[nc][i]]][j].second] == true) {
				T[R[num[NT[nc][i]]][j].second].push_back(num[NT[nc][i]]);
				break;
			}
		}
	}
	
	for(int i = 0; i < C.size(); i++){
		if(C[(i+1)%C.size()] == e.first) continue;
		T[C[i]].push_back(C[(i+1)%C.size()]);
		cost += R[C[(i+1)%C.size()]][0].first;
	}
	
	return T;
}


signed main(){
	cout<<fixed<<setprecision(10);
	
	while(true) {
		int N;
		int cost = 0;
		vector<vector<pair<int,int>>> G;
		
		cin>>N;
		
		if(!N) break;
		
		G.resize(N+1);
		
		for(int i = 1; i <= N; i++){
			for(int j = 0; j <= N; j++){
				int t;
				
				cin>>t;
				
				G[j].push_back({i, t});
			}
		}
		
		Chu_Liu_Edmonds(G, 0, cost);
		
		cout<<cost<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 3324