#include <cstdio>
#include <iostream>
#include <map>
using namespace std;

typedef pair<int,int> PII;
typedef map<PII,int> Cache;

// Adjacency matrix. As all edges are supplied, there is no impossible
// value.
int edges[15][15];

Cache cache;

// This will determine the minimum distance needed to finish the
// deliveries and return home given the number of nodes, the bitmask
// of visited nodes, and the current node.
int solve(int n, int hit, int at) {

  // Check the cache to see if (hit,at) have already been encountered...
  Cache::iterator it = cache.find(PII(hit,at));
  if (it != cache.end()) return it->second;

  // If we have visited all nodes, we simply return home.
  if (hit == (1<<n)-1) { return edges[at][0]; }

  // Recursively solve from each unvisited house...
  int best = INT_MAX/2;
  for (int i = 0; i < n; ++i) {
    if ((hit & (1<<i)) == 0) {
      best = min(best, solve(n, hit | (1<<i), i) + edges[at][i]);
    }
  }
  return cache[PII(hit,at)] = best;
}

int main(void) {
  for (int casei = 1; ; ++casei) {
    int n; cin >> n;
    if (n == 0) break;

    // Increment the number of nodes so that they are 0..(n-1) with 0
    // being the pizzaria.
    n += 1;

    for (int f = 0; f < n; ++f) {
      for (int t = 0; t < n; ++t) {
	cin >> edges[f][t];
      }
    }
    
    // Floyd-Warshall in five lines. This is necessary to make sure
    // the 'return home' in solve uses the shortest possible path.
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
	for (int k = 0; k < n; ++k)
	  edges[i][j] = min(edges[i][j],
			    edges[i][k] + edges[k][j]);
    
    cache.clear();

    // Start the search having visited only the pizzaria, and at the pizzaria.
    printf("%d\n", solve(n,1,0));
  }
  return 0;
}