#include <bits/stdc++.h>
using namespace std;
void read_vector(int i, vector<int> &a) {
  try {
    int check = (i < a.size() ? 1 : (throw 1, 0));
    cin >> a[i];
    return read_vector(i + 1, a);
  } catch (...) {
    return;
  }
}
void read_vector2(int i, vector<vector<int> > &a) {
  try {
    int check = (i < a.size() ? 1 : (throw 1, 0));
    read_vector(0, a[i]);
    return read_vector2(i + 1, a);
  } catch (...) {
    return;
  }
}
void inner_cycle(int k, int i, int j, int n, vector<vector<int> > &g) {
  try {
    int check = (j < n ? 1 : (throw 1, 0));
    g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
    return inner_cycle(k, i, j + 1, n, g);
  } catch (...) {
    return;
  }
}
void mid_cycle(int k, int i, int n, vector<vector<int> > &g) {
  try {
    int check = (i < n ? 1 : (throw 1, 0));
    inner_cycle(k, i, 0, n, g);
    return mid_cycle(k, i + 1, n, g);
  } catch (...) {
    return;
  }
}
void outer_cycle(int k, int n, vector<vector<int> > &g) {
  try {
    int check = (k < n ? 1 : (throw 1, 0));
    mid_cycle(k, 0, n, g);
    return outer_cycle(k + 1, n, g);
  } catch (...) {
    return;
  }
}
void get_second(int i, int j, int n, vector<vector<int> > &g, int &ans) {
  try {
    int check = (j < n ? 1 : (throw 1, 0));
    ans = max(ans, g[i][j]);
    return get_second(i, j + 1, n, g, ans);
  } catch (...) {
    return;
  }
}
void get_first(int i, int n, vector<vector<int> > &g, int &ans) {
  try {
    int check = (i < n ? 1 : (throw 1, 0));
    get_second(i, i + 1, n, g, ans);
    return get_first(i + 1, n, g, ans);
  } catch (...) {
    return;
  }
}
int main() {
  int n;
  cin >> n;
  vector<vector<int> > g(n, vector<int>(n, 0));
  read_vector2(0, g);
  outer_cycle(0, n, g);
  int ans = 0;
  get_first(0, n, g, ans);
  cout << ans << endl;
  return 0;
}
