#include <bits/stdc++.h>
using namespace std;
int n;
int d[111];
void read();
void h(int k, int i, int j) {
  d[i * n + j] = max(max(i, j), k) < n
                     ? min(d[i * n + j], d[i * n + k] + d[k * n + j])
                     : d[i * n + j];
}
void g(int k, int i) {
  h(k, i, 0);
  h(k, i, 1);
  h(k, i, 2);
  h(k, i, 3);
  h(k, i, 4);
  h(k, i, 5);
  h(k, i, 6);
  h(k, i, 7);
  h(k, i, 8);
  h(k, i, 9);
}
void f(int k) {
  g(k, 0);
  g(k, 1);
  g(k, 2);
  g(k, 3);
  g(k, 4);
  g(k, 5);
  g(k, 6);
  g(k, 7);
  g(k, 8);
  g(k, 9);
}
int main() {
  cin >> n;
  read();
  f(0);
  f(1);
  f(2);
  f(3);
  f(4);
  f(5);
  f(6);
  f(7);
  f(8);
  f(9);
  printf("%d\n", *max_element(d, d + n * n));
  return 0;
}
void read() {
  cin >> d[0];
  cin >> d[1];
  cin >> d[2];
  cin >> d[3];
  cin >> d[4];
  cin >> d[5];
  cin >> d[6];
  cin >> d[7];
  cin >> d[8];
  cin >> d[9];
  cin >> d[10];
  cin >> d[11];
  cin >> d[12];
  cin >> d[13];
  cin >> d[14];
  cin >> d[15];
  cin >> d[16];
  cin >> d[17];
  cin >> d[18];
  cin >> d[19];
  cin >> d[20];
  cin >> d[21];
  cin >> d[22];
  cin >> d[23];
  cin >> d[24];
  cin >> d[25];
  cin >> d[26];
  cin >> d[27];
  cin >> d[28];
  cin >> d[29];
  cin >> d[30];
  cin >> d[31];
  cin >> d[32];
  cin >> d[33];
  cin >> d[34];
  cin >> d[35];
  cin >> d[36];
  cin >> d[37];
  cin >> d[38];
  cin >> d[39];
  cin >> d[40];
  cin >> d[41];
  cin >> d[42];
  cin >> d[43];
  cin >> d[44];
  cin >> d[45];
  cin >> d[46];
  cin >> d[47];
  cin >> d[48];
  cin >> d[49];
  cin >> d[50];
  cin >> d[51];
  cin >> d[52];
  cin >> d[53];
  cin >> d[54];
  cin >> d[55];
  cin >> d[56];
  cin >> d[57];
  cin >> d[58];
  cin >> d[59];
  cin >> d[60];
  cin >> d[61];
  cin >> d[62];
  cin >> d[63];
  cin >> d[64];
  cin >> d[65];
  cin >> d[66];
  cin >> d[67];
  cin >> d[68];
  cin >> d[69];
  cin >> d[70];
  cin >> d[71];
  cin >> d[72];
  cin >> d[73];
  cin >> d[74];
  cin >> d[75];
  cin >> d[76];
  cin >> d[77];
  cin >> d[78];
  cin >> d[79];
  cin >> d[80];
  cin >> d[81];
  cin >> d[82];
  cin >> d[83];
  cin >> d[84];
  cin >> d[85];
  cin >> d[86];
  cin >> d[87];
  cin >> d[88];
  cin >> d[89];
  cin >> d[90];
  cin >> d[91];
  cin >> d[92];
  cin >> d[93];
  cin >> d[94];
  cin >> d[95];
  cin >> d[96];
  cin >> d[97];
  cin >> d[98];
  cin >> d[99];
}
