#include <bits/stdc++.h>
using namespace std;
int n;
int ans = -1e9;
vector<int> v;
int F(int i) {
  int t;
  cin >> t;
  v.push_back(t);
  return (i - 1) ? F(i - 1) : 0;
}
int F4(int i, int j, int k) {
  v[(j - 1) * n + k - 1] = min(v[(j - 1) * n + k - 1],
                               v[(j - 1) * n + i - 1] + v[(i - 1) * n + k - 1]);
  return (k - 1) ? F4(i, j, k - 1) : 0;
}
int F3(int i, int j) {
  F4(i, j, n);
  return (j - 1) ? F3(i, j - 1) : 0;
}
int F2(int i) {
  F3(i, n);
  return (i - 1) ? F2(i - 1) : 0;
}
int F5(int i) {
  ans = max(ans, v[i - 1]);
  return (i - 1) ? F5(i - 1) : 0;
}
int main() {
  cin >> n;
  F(n * n);
  F2(n);
  F5(n * n);
  cout << ans;
}
