#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

typedef int Weight;
struct Edge {
  int src;
  int dest;
  Weight weight;
  Edge(int src, int dest, Weight weight) : src(src), dest(dest), weight(weight) {;}
  bool operator<(const Edge &rhs) const {
    if (weight != rhs.weight) { return weight > rhs.weight; }
    if (src != rhs.src) { return src < rhs.src; }
    return dest < rhs.dest;
  }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void PrintMatrix(const Matrix &matrix) {
  for (int y = 0; y < (int)matrix.size(); y++) {
    for (int x = 0; x < (int)matrix[y].size(); x++) {
      printf("%d ", matrix[y][x]);
    }
    puts("");
  }
}


void SccDfs(const Graph &g, int from, vector<int> &visit, vector<int> &st) {
  visit[from] = 1;
  for (Edges::const_iterator it = g[from].begin(); it != g[from].end(); it++) {
    if (visit[it->dest]) { continue; }
    SccDfs(g, it->dest, visit, st);
  }
  st.push_back(from);
}

vector<vector<int> > Scc(const Graph &g) {
  const int n = g.size();
  vector<vector<int> > ret;
  Graph revg(n);
  for (int i = 0; i < n; i++) {
    for (Edges::const_iterator it = g[i].begin(); it != g[i].end(); it++) {
      revg[it->dest].push_back(Edge(it->dest, i, it->weight));
    }
  }
  vector<int> st;
  vector<int> visit(n, 0);
  for (int i = 0; i < n; i++) {
    if (visit[i]) { continue; }
    SccDfs(g, i, visit, st);
  }
  visit = vector<int>(n, 0);
  for (int i = n - 1; i >= 0; i--) {
    int index = st[i];
    if (visit[index]) { continue; }
    vector<int> nret;
    SccDfs(revg, index, visit, nret);
    ret.push_back(nret);
  }
  return ret;
}

// need Scc
Weight Arborescence(const Graph &g, int root) {
  const int n = g.size();
  Weight ret = 0;
  vector<Weight> inCost(n, 1000000000LL);
  vector<int> parent(n, -1);
  for (int from = 0; from < n; from++) {
    for (Edges::const_iterator it = g[from].begin(); it != g[from].end(); it++) {
      if (it->dest == from) { continue; }
      if (it->weight < inCost[it->dest]) {
        parent[it->dest] = from;
        inCost[it->dest] = it->weight;
      }
      inCost[it->dest] = min(inCost[it->dest], it->weight);
    }
  }
  Graph ng(n);
  for (int i = 0; i < n; i++) {
    if (i == root) { continue; }
    if (parent[i] == -1) { return 1000000000LL; }
    ng[parent[i]].push_back(Edge(parent[i], i, 0));
    ret += inCost[i];
  }
  vector<vector<int> > connect = Scc(ng);
  int m = connect.size();
  if (m == n) { return ret; }
  vector<int> mapto(n, -1);
  vector<int> cycle(n, 0);
  ret = 0;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < (int)connect[i].size(); j++) {
      mapto[connect[i][j]] = i;
      if (connect[i].size() != 1) {
        cycle[connect[i][j]] = 1;
        ret += inCost[connect[i][j]];
      }
    }
  }
  ng = Graph(m);
  for (int from = 0; from < n; from++) {
    for (Edges::const_iterator it = g[from].begin(); it != g[from].end(); it++) {
      int to = it->dest;
      if (to == root || mapto[from] == mapto[to]) { continue; }
      Weight cost = it->weight;
      if (cycle[to]) {
        cost -= inCost[to];
      }
      ng[mapto[from]].push_back(Edge(mapto[from], mapto[to], cost));
    }
  }
  return min(1000000000, ret + Arborescence(ng, mapto[root]));
}

int n;
int main() {
  while (scanf("%d", &n), n) {
    Graph g(n + 1);
    REP(i, n) {
      int t;
      scanf("%d", &t);
      g[n].push_back(Edge(n, i, t));
      REP(j, n) {
        scanf("%d", &t);
        g[j].push_back(Edge(j, i, t));
      }
    }
    printf("%d\n", Arborescence(g, n));
  }
}

Measured memory_bytes: 0