#include <bits/stdc++.h>
using namespace std;
int n, s, t, Ans;
int a[105][15];
int dist[1005];
bool pd0(int x) { return x <= n ? true : false; }
int get() {
  scanf("%d", &a[s][t]), t++;
  s += (pd0(t) ^ 1);
  t -= (pd0(t) ^ 1) * n;
  return 0;
}
int work(int x, int len) {
  dist[x] = min(dist[x], len);
  int t;
  t = (dist[1] > dist[x] + a[x][1] && x <= n) ? work(1, len + a[x][1]) : 0;
  t = (dist[2] > dist[x] + a[x][2] && x <= n) ? work(2, len + a[x][2]) : 0;
  t = (dist[3] > dist[x] + a[x][3] && x <= n) ? work(3, len + a[x][3]) : 0;
  t = (dist[4] > dist[x] + a[x][4] && x <= n) ? work(4, len + a[x][4]) : 0;
  t = (dist[5] > dist[x] + a[x][5] && x <= n) ? work(5, len + a[x][5]) : 0;
  t = (dist[6] > dist[x] + a[x][6] && x <= n) ? work(6, len + a[x][6]) : 0;
  t = (dist[7] > dist[x] + a[x][7] && x <= n) ? work(7, len + a[x][7]) : 0;
  t = (dist[8] > dist[x] + a[x][8] && x <= n) ? work(8, len + a[x][8]) : 0;
  t = (dist[9] > dist[x] + a[x][9] && x <= n) ? work(9, len + a[x][9]) : 0;
  t = (dist[10] > dist[x] + a[x][10] && x <= n) ? work(10, len + a[x][10]) : 0;
  return 1;
}
void getans() {
  Ans = max(Ans, dist[1] != dist[666] ? dist[1] : -1);
  Ans = max(Ans, dist[2] != dist[666] ? dist[2] : -1);
  Ans = max(Ans, dist[3] != dist[666] ? dist[3] : -1);
  Ans = max(Ans, dist[4] != dist[666] ? dist[4] : -1);
  Ans = max(Ans, dist[5] != dist[666] ? dist[5] : -1);
  Ans = max(Ans, dist[6] != dist[666] ? dist[6] : -1);
  Ans = max(Ans, dist[7] != dist[666] ? dist[7] : -1);
  Ans = max(Ans, dist[8] != dist[666] ? dist[8] : -1);
  Ans = max(Ans, dist[9] != dist[666] ? dist[9] : -1);
  Ans = max(Ans, dist[10] != dist[666] ? dist[10] : -1);
}
int main() {
  int i, j, o;
  scanf("%d", &n);
  s = t = 1;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  o = (s <= n && t <= n) ? get() : 3;
  memset(dist, 62, sizeof(dist));
  dist[1] = 0;
  work(1, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[2] = 0;
  work(2, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[3] = 0;
  work(3, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[4] = 0;
  work(4, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[5] = 0;
  work(5, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[6] = 0;
  work(6, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[7] = 0;
  work(7, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[8] = 0;
  work(8, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[9] = 0;
  work(9, 0);
  getans();
  memset(dist, 62, sizeof(dist));
  dist[10] = 0;
  work(10, 0);
  getans();
  cout << Ans << endl;
  return 0;
}
