#include <bits/stdc++.h>
using namespace std;
int mas[10][10];
int n;
void init(int x, int y);
void lol() { return; }
void kek(int x, int y) { (x + 1 < n ? (init(x + 1, 0)) : lol()); }
void init(int x, int y) {
  cin >> mas[x][y];
  (y + 1 < n ? (init(x, y + 1)) : kek(x, y));
}
void f3(int x, int y, int k) {
  mas[x][y] = min(mas[x][y], mas[x][k] + mas[k][y]);
  (y + 1 < n ? (f3(x, y + 1, k)) : lol());
}
void f2(int x, int k) { (x < n ? (f3(x, 0, k), f2(x + 1, k)) : lol()); }
void f1(int k) { (k < n ? (f2(0, k), f1(k + 1)) : (lol())); }
int minn;
void heh(int x, int y);
void hah(int x, int y) { (x + 1 < n ? (heh(x + 1, 0)) : lol()); }
void heh(int x, int y) {
  minn = max(minn, mas[x][y]);
  (y + 1 < n ? (heh(x, y + 1)) : hah(x, y));
}
int main() {
  cin >> n;
  init(0, 0);
  f1(0);
  heh(0, 0);
  cout << minn;
}
