#include <bits/stdc++.h>
using namespace std;
int result = 0;
int n;
int tab[20][20];
void nothingFunc() {}
void solvingFunc();
void maximizingFunc();
void printFunc();
void (*foo[2])(void) = {nothingFunc, solvingFunc};
void (*foofoo[2])(void) = {nothingFunc, maximizingFunc};
void (*foofoofoo[2])(void) = {nothingFunc, printFunc};
void solvingFunc() {
  int i = 0, j = 0, k = 0;
solving : {
  tab[j][k] = min(tab[j][k], tab[j][i] + tab[i][k]);
  k++;
  j += (k / n);
  k %= n;
  i += (j / n);
  j %= n;
  foofoo[i / n]();
  goto solving;
}
}
void maximizingFunc() {
  int i = 0, j = 0;
maximizing : {
  result = max(result, tab[i][j]);
  j++;
  i += (j / n);
  j %= n;
  foofoofoo[i / n]();
  goto maximizing;
}
}
void printFunc() {
  cout << result;
  exit(0);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n;
  int i = 0, j = 0;
reading : {
  cin >> tab[i][j];
  j++;
  i += (j / n);
  j %= n;
  foo[i / n]();
  goto reading;
}
  return 0;
}
