#include <bits/stdc++.h>
int n, ans, a[15][15];
inline void maxx(int& a, int b) { a = (a > b ? a : b); }
inline void minx(int& a, int b) { a = (a < b ? a : b); }
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) minx(a[i][j], a[i][k] + a[k][j]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) maxx(ans, a[i][j]);
  printf("%d\n", ans);
  return 0;
}
