//#include "bits/stdc++.h"

#include <iostream>
#include <vector>
#include <set>
#include <queue>
// #include <string>
// #include <algorithm>
// #include <numeric>
#include <limits>

using namespace std;

using Matrix = vector<vector<int>>; // [stage][equip]
using Node = vector<int>; // Node[0] is 0 (dummy), Node[i] is 1 (if stage i is remain), 0 (otherwise)

int n;
Matrix mat;
vector<int> min_time;

struct State;
void print(const State& state);

struct State {
	Node node;
	int f = -1;
	int g = -1;
	int h = -1;

	State(Node _node) : node(_node) {
		f = 0;
		g = 0;
		h = 0;
	}

	int calcCost(const State& bef, int stage) const {
		int min_cost = mat[stage][0];
		for (int equip = 1; equip <= n; equip++) {
			if (bef.node[equip] == 0) {
				continue;
			}
			min_cost = min(min_cost, mat[stage][equip]);
		}
		return min_cost;
	}

	// consistemt
	int heuristic() const {
		int cost = 0;
		for (int stage = 1; stage <= n; stage++) {
			if (node[stage] == 1) {
				continue;
			}
			cost += min_time[stage];
		}
		return cost;
	}

	State(const State& bef, int stage) : node(bef.node) {
		node[stage] = 1;
		g = bef.g + calcCost(bef, stage);
		h = heuristic();
		f = g + h;
	}
};

bool operator < (const State& a, const State& b) {
	return a.f > b.f;
}

size_t size;
set<Node> open_close_list;
priority_queue<State> p_que;


void print(Matrix& mat) {
	for (size_t stage = 1; stage < mat.size(); stage++) {
		for (size_t equip = 0; equip < mat[stage].size(); equip++) {
			cout << " " << mat[stage][equip];
		}
		cout << endl;
	}
}

void print(const State& state) {
	cout << "---" << endl;
	for (auto v : state.node) {
		cout << v << " ";
	}
	cout << endl;
	cout << "  " << state.f << " " << state.g << " " << state.h << endl;
}

void input() {
	size = n + 1;
	mat = vector<vector<int>>(size, vector<int>(size, 0)); // mat[stage][equip]
	min_time.resize(size);
	for (size_t stage = 1; stage < size; stage++) {
		min_time[stage] = numeric_limits<int>::max();
		for (size_t equip = 0; equip < size; equip++) {
			cin >> mat[stage][equip];
			if (stage != equip) {
				min_time[stage] = min(min_time[stage], mat[stage][equip]);
			}
		}
	}
	// print(mat); // debug
}

bool isGoal(const Node& node) {
	for (int stage = 1; stage <= n; stage++) {
		if (node[stage] == 0) {
			return false;
		}
	}
	return true;
}

void clearPQue() {
	while (p_que.empty() == false) {
		p_que.pop();
	}	
}

int solve() {
	open_close_list.clear();
	clearPQue();
	input();
	Node start_node = Node(size, 0);
	open_close_list.insert(start_node);
	State start(start_node);
	p_que.push(start);
	while (p_que.empty() == false) {
		State now = p_que.top();
		p_que.pop();
		// std::cout << "debug now" << std::endl; // debug
		// print(now); // debug
		for (int stage = 1; stage <= n; stage++) {
			if (now.node[stage] == 1) {
				continue;
			}
			State next(now, stage);
			// std::cout << "debug next" << std::endl; // debug
			// print(next); // debug
			if (open_close_list.count(next.node)) {
				continue;
			}
			open_close_list.insert(next.node);
			if (isGoal(next.node)) {
				return next.f;
			}
			p_que.push(next);
		}
	}
	return -1;
}

int main() {
	while (1) {
		cin >> n;
		if (n == 0) {
			break;
		}
		cout << solve() << endl;
	}

	// std::cout << "\e[38;5;0m\e[48;5;40m --- end ---  \e[m" << std::endl; // debug
	return 0;
}

Measured memory_bytes: 6964