#include <bits/stdc++.h>
using namespace std;
int d[15][15];
int V;
void w() {
  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }
  }
}
void solve() {
  w();
  int ans = 0;
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      ans = max(ans, d[i][j]);
    }
  }
  printf("%d\n", ans);
}
int main() {
  scanf("%d", &V);
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      scanf("%d", &d[i][j]);
    }
  }
  solve();
}
