#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > a;
vector<vector<int> > dist;
vector<int> idx2, idx3;
int id;
int N;
int res = 0;
const int INF = 100 + 1;
void f2(int i) { idx2[id] = id++; }
void f3(int i) { idx3[id] = id++; }
void f_input(int x) {
  int i = x / N;
  int j = x % N;
  cin >> a[i][j];
  dist[i][j] = a[i][j];
}
void f_fw(int x) {
  int k = x / (N * N);
  x -= k * N * N;
  int i = x / N;
  int j = x % N;
  dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
void f_res(int x) {
  int i = x / N;
  int j = x % N;
  res = max(res, dist[i][j]);
}
int main(int argc, char **argv) {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0), cout.precision(15);
  cin >> N;
  a = vector<vector<int> >(N, vector<int>(N));
  dist = vector<vector<int> >(N, vector<int>(N, INF));
  idx2.resize(N * N);
  idx3.resize(N * N * N);
  id = 0;
  for_each(idx2.begin(), idx2.end(), f2);
  id = 0;
  for_each(idx3.begin(), idx3.end(), f3);
  for_each(idx2.begin(), idx2.end(), f_input);
  for_each(idx3.begin(), idx3.end(), f_fw);
  for_each(idx2.begin(), idx2.end(), f_res);
  cout << res << endl;
  return 0;
}
