//* Problem  : 2562 - Hie with the Pie 
//* Contest  : acm.tju.edu.cn
//* Origin   : East Central North America 2006
//* Type     : Solution
//* Date     : 2008.04.28
//* Author   : alt
//* Language : C++
//* Compiler : Microsoft Visual C++ 6.0
//* Algoritm : 

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define int64 long long

int n;

int a[16][16], u[16], res, cnt;
int st[16];

/*
void gamilt(int v, int cost)
{
	if (cost > res)  return;
	if (cnt == n)
	{
		cost += a[v][1];
		if (cost < res)
			res = cost;
		return;
	}
	for (int i = 2; i <= n; i++)
		if (!u[i])
		{
			cnt++; u[i] = 1; gamilt(i, cost + a[v][i]); u[i] = 0; cnt--;
		}
}
*/

void gamilt11(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt11(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt10(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt11(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt9(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt10(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt8(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt9(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt7(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt8(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt6(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt7(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt5(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt6(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt4(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt5(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt3(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt4(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt2(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt3(i, cost + a[v][i]); u[i] = 0; cnt--;}}
inline void gamilt1(int v, int cost){if (cost > res) return; if (cnt == n){cost += a[v][1];if (cost < res)res = cost;return;}for (int i = 2; i <= n; i++)if (!u[i]){cnt++; u[i] = 1; gamilt2(i, cost + a[v][i]); u[i] = 0; cnt--;}}

void solve()
{
	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (a[i][j] > a[i][k] + a[k][j])
					a[i][j] = a[i][k] + a[k][j];
	res = 1000000000;
	cnt = 1; u[1] = 1; st[1] = 1;
	gamilt1(1, 0);
}

int main()
{
	while (scanf("%d", &n) && n)
	{
		n++;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				scanf("%d", &a[i][j]);
		solve();
		printf("%d\n", res);
	}
	return 0;
}