You are given a complete undirected graph. For each pair of vertices you are given the length of the edge that connects them. Find the shortest paths between each pair of vertices in the graph and return the length of the longest of them.

Input

The first line of the input contains a single integer N (3 ≤ N ≤ 10).

The following N lines each contain N space-separated integers. jth integer in ith line aij is the length of the edge that connects vertices i and j. aij = aji, aii = 0, 1 ≤ aij ≤ 100 for i ≠ j.

Output

Output the maximum length of the shortest path between any pair of vertices in the graph.

Examples

Input

3
0 1 1
1 0 4
1 4 0


Output

2


Input

4
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0


Output

5

Note

You're running short of keywords, so you can't use some of them:
    
    
    define  
    do  
    for  
    foreach  
    while  
    repeat  
    until  
    if  
    then  
    else  
    elif  
    elsif  
    elseif  
    case  
    switch  
    
#include <bits/stdc++.h>
using namespace std;
int a;
int b;
int c;
int d;
int e;
int f;
int g;
int h;
int i;
int j;
int k;
int l;
int m;
int n;
int o;
int p;
int q;
int r;
int s;
int t;
int u;
int v;
int w;
int x;
int y;
int z;
int A;
int B;
int C;
int D;
int E;
int F;
int G;
int H;
int I;
int J;
int K;
int L;
int M;
int N;
int O;
int P;
int Q;
int R;
int S;
int T;
int U;
int V;
int W;
int X;
int Y;
int Z;
int a5;
int b5;
int c5;
int d5;
int e5;
int f5;
int g5;
int h5;
int i5;
int j5;
int k5;
int l5;
int m5;
int n5;
int o5;
int p5;
int q5;
int r5;
int s5;
int t5;
int u5;
int v5;
int w5;
int x5;
int y5;
int z5;
int A5;
int B5;
int C5;
int D5;
int E5;
int F5;
int G5;
int H5;
int I5;
int J5;
int K5;
int L5;
int M5;
int N5;
int O5;
int P5;
int Q5;
int R5;
int S5;
int T5;
int U5;
int V5;
int _n;
void solve1() {
  a = min(a, a + a);
  int _a = 0;
  _a = max(_a, a);
  printf("%d\n", _a);
}
void solve2() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, c + a);
  d = min(d, c + b);
  a = min(a, b + c);
  b = min(b, b + d);
  c = min(c, d + c);
  d = min(d, d + d);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  printf("%d\n", _a);
}
void solve3() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, a + c);
  d = min(d, d + a);
  e = min(e, d + b);
  f = min(f, d + c);
  g = min(g, g + a);
  h = min(h, g + b);
  i = min(i, g + c);
  a = min(a, b + d);
  b = min(b, b + e);
  c = min(c, b + f);
  d = min(d, e + d);
  e = min(e, e + e);
  f = min(f, e + f);
  g = min(g, h + d);
  h = min(h, h + e);
  i = min(i, h + f);
  a = min(a, c + g);
  b = min(b, c + h);
  c = min(c, c + i);
  d = min(d, f + g);
  e = min(e, f + h);
  f = min(f, f + i);
  g = min(g, i + g);
  h = min(h, i + h);
  i = min(i, i + i);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  _a = max(_a, e);
  _a = max(_a, f);
  _a = max(_a, g);
  _a = max(_a, h);
  _a = max(_a, i);
  printf("%d\n", _a);
}
void solve4() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, a + c);
  d = min(d, a + d);
  e = min(e, e + a);
  f = min(f, e + b);
  g = min(g, e + c);
  h = min(h, e + d);
  i = min(i, i + a);
  j = min(j, i + b);
  k = min(k, i + c);
  l = min(l, i + d);
  m = min(m, m + a);
  n = min(n, m + b);
  o = min(o, m + c);
  p = min(p, m + d);
  a = min(a, b + e);
  b = min(b, b + f);
  c = min(c, b + g);
  d = min(d, b + h);
  e = min(e, f + e);
  f = min(f, f + f);
  g = min(g, f + g);
  h = min(h, f + h);
  i = min(i, j + e);
  j = min(j, j + f);
  k = min(k, j + g);
  l = min(l, j + h);
  m = min(m, n + e);
  n = min(n, n + f);
  o = min(o, n + g);
  p = min(p, n + h);
  a = min(a, c + i);
  b = min(b, c + j);
  c = min(c, c + k);
  d = min(d, c + l);
  e = min(e, g + i);
  f = min(f, g + j);
  g = min(g, g + k);
  h = min(h, g + l);
  i = min(i, k + i);
  j = min(j, k + j);
  k = min(k, k + k);
  l = min(l, k + l);
  m = min(m, o + i);
  n = min(n, o + j);
  o = min(o, o + k);
  p = min(p, o + l);
  a = min(a, d + m);
  b = min(b, d + n);
  c = min(c, d + o);
  d = min(d, d + p);
  e = min(e, h + m);
  f = min(f, h + n);
  g = min(g, h + o);
  h = min(h, h + p);
  i = min(i, l + m);
  j = min(j, l + n);
  k = min(k, l + o);
  l = min(l, l + p);
  m = min(m, p + m);
  n = min(n, p + n);
  o = min(o, p + o);
  p = min(p, p + p);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  _a = max(_a, e);
  _a = max(_a, f);
  _a = max(_a, g);
  _a = max(_a, h);
  _a = max(_a, i);
  _a = max(_a, j);
  _a = max(_a, k);
  _a = max(_a, l);
  _a = max(_a, m);
  _a = max(_a, n);
  _a = max(_a, o);
  _a = max(_a, p);
  printf("%d\n", _a);
}
void solve5() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, a + c);
  d = min(d, a + d);
  e = min(e, a + e);
  f = min(f, f + a);
  g = min(g, f + b);
  h = min(h, f + c);
  i = min(i, f + d);
  j = min(j, f + e);
  k = min(k, k + a);
  l = min(l, k + b);
  m = min(m, k + c);
  n = min(n, k + d);
  o = min(o, k + e);
  p = min(p, p + a);
  q = min(q, p + b);
  r = min(r, p + c);
  s = min(s, p + d);
  t = min(t, p + e);
  u = min(u, u + a);
  v = min(v, u + b);
  w = min(w, u + c);
  x = min(x, u + d);
  y = min(y, u + e);
  a = min(a, b + f);
  b = min(b, b + g);
  c = min(c, b + h);
  d = min(d, b + i);
  e = min(e, b + j);
  f = min(f, g + f);
  g = min(g, g + g);
  h = min(h, g + h);
  i = min(i, g + i);
  j = min(j, g + j);
  k = min(k, l + f);
  l = min(l, l + g);
  m = min(m, l + h);
  n = min(n, l + i);
  o = min(o, l + j);
  p = min(p, q + f);
  q = min(q, q + g);
  r = min(r, q + h);
  s = min(s, q + i);
  t = min(t, q + j);
  u = min(u, v + f);
  v = min(v, v + g);
  w = min(w, v + h);
  x = min(x, v + i);
  y = min(y, v + j);
  a = min(a, c + k);
  b = min(b, c + l);
  c = min(c, c + m);
  d = min(d, c + n);
  e = min(e, c + o);
  f = min(f, h + k);
  g = min(g, h + l);
  h = min(h, h + m);
  i = min(i, h + n);
  j = min(j, h + o);
  k = min(k, m + k);
  l = min(l, m + l);
  m = min(m, m + m);
  n = min(n, m + n);
  o = min(o, m + o);
  p = min(p, r + k);
  q = min(q, r + l);
  r = min(r, r + m);
  s = min(s, r + n);
  t = min(t, r + o);
  u = min(u, w + k);
  v = min(v, w + l);
  w = min(w, w + m);
  x = min(x, w + n);
  y = min(y, w + o);
  a = min(a, d + p);
  b = min(b, d + q);
  c = min(c, d + r);
  d = min(d, d + s);
  e = min(e, d + t);
  f = min(f, i + p);
  g = min(g, i + q);
  h = min(h, i + r);
  i = min(i, i + s);
  j = min(j, i + t);
  k = min(k, n + p);
  l = min(l, n + q);
  m = min(m, n + r);
  n = min(n, n + s);
  o = min(o, n + t);
  p = min(p, s + p);
  q = min(q, s + q);
  r = min(r, s + r);
  s = min(s, s + s);
  t = min(t, s + t);
  u = min(u, x + p);
  v = min(v, x + q);
  w = min(w, x + r);
  x = min(x, x + s);
  y = min(y, x + t);
  a = min(a, e + u);
  b = min(b, e + v);
  c = min(c, e + w);
  d = min(d, e + x);
  e = min(e, e + y);
  f = min(f, j + u);
  g = min(g, j + v);
  h = min(h, j + w);
  i = min(i, j + x);
  j = min(j, j + y);
  k = min(k, o + u);
  l = min(l, o + v);
  m = min(m, o + w);
  n = min(n, o + x);
  o = min(o, o + y);
  p = min(p, t + u);
  q = min(q, t + v);
  r = min(r, t + w);
  s = min(s, t + x);
  t = min(t, t + y);
  u = min(u, y + u);
  v = min(v, y + v);
  w = min(w, y + w);
  x = min(x, y + x);
  y = min(y, y + y);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  _a = max(_a, e);
  _a = max(_a, f);
  _a = max(_a, g);
  _a = max(_a, h);
  _a = max(_a, i);
  _a = max(_a, j);
  _a = max(_a, k);
  _a = max(_a, l);
  _a = max(_a, m);
  _a = max(_a, n);
  _a = max(_a, o);
  _a = max(_a, p);
  _a = max(_a, q);
  _a = max(_a, r);
  _a = max(_a, s);
  _a = max(_a, t);
  _a = max(_a, u);
  _a = max(_a, v);
  _a = max(_a, w);
  _a = max(_a, x);
  _a = max(_a, y);
  printf("%d\n", _a);
}
void solve6() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, a + c);
  d = min(d, a + d);
  e = min(e, a + e);
  f = min(f, a + f);
  g = min(g, g + a);
  h = min(h, g + b);
  i = min(i, g + c);
  j = min(j, g + d);
  k = min(k, g + e);
  l = min(l, g + f);
  m = min(m, m + a);
  n = min(n, m + b);
  o = min(o, m + c);
  p = min(p, m + d);
  q = min(q, m + e);
  r = min(r, m + f);
  s = min(s, s + a);
  t = min(t, s + b);
  u = min(u, s + c);
  v = min(v, s + d);
  w = min(w, s + e);
  x = min(x, s + f);
  y = min(y, y + a);
  z = min(z, y + b);
  A = min(A, y + c);
  B = min(B, y + d);
  C = min(C, y + e);
  D = min(D, y + f);
  E = min(E, E + a);
  F = min(F, E + b);
  G = min(G, E + c);
  H = min(H, E + d);
  I = min(I, E + e);
  J = min(J, E + f);
  a = min(a, b + g);
  b = min(b, b + h);
  c = min(c, b + i);
  d = min(d, b + j);
  e = min(e, b + k);
  f = min(f, b + l);
  g = min(g, h + g);
  h = min(h, h + h);
  i = min(i, h + i);
  j = min(j, h + j);
  k = min(k, h + k);
  l = min(l, h + l);
  m = min(m, n + g);
  n = min(n, n + h);
  o = min(o, n + i);
  p = min(p, n + j);
  q = min(q, n + k);
  r = min(r, n + l);
  s = min(s, t + g);
  t = min(t, t + h);
  u = min(u, t + i);
  v = min(v, t + j);
  w = min(w, t + k);
  x = min(x, t + l);
  y = min(y, z + g);
  z = min(z, z + h);
  A = min(A, z + i);
  B = min(B, z + j);
  C = min(C, z + k);
  D = min(D, z + l);
  E = min(E, F + g);
  F = min(F, F + h);
  G = min(G, F + i);
  H = min(H, F + j);
  I = min(I, F + k);
  J = min(J, F + l);
  a = min(a, c + m);
  b = min(b, c + n);
  c = min(c, c + o);
  d = min(d, c + p);
  e = min(e, c + q);
  f = min(f, c + r);
  g = min(g, i + m);
  h = min(h, i + n);
  i = min(i, i + o);
  j = min(j, i + p);
  k = min(k, i + q);
  l = min(l, i + r);
  m = min(m, o + m);
  n = min(n, o + n);
  o = min(o, o + o);
  p = min(p, o + p);
  q = min(q, o + q);
  r = min(r, o + r);
  s = min(s, u + m);
  t = min(t, u + n);
  u = min(u, u + o);
  v = min(v, u + p);
  w = min(w, u + q);
  x = min(x, u + r);
  y = min(y, A + m);
  z = min(z, A + n);
  A = min(A, A + o);
  B = min(B, A + p);
  C = min(C, A + q);
  D = min(D, A + r);
  E = min(E, G + m);
  F = min(F, G + n);
  G = min(G, G + o);
  H = min(H, G + p);
  I = min(I, G + q);
  J = min(J, G + r);
  a = min(a, d + s);
  b = min(b, d + t);
  c = min(c, d + u);
  d = min(d, d + v);
  e = min(e, d + w);
  f = min(f, d + x);
  g = min(g, j + s);
  h = min(h, j + t);
  i = min(i, j + u);
  j = min(j, j + v);
  k = min(k, j + w);
  l = min(l, j + x);
  m = min(m, p + s);
  n = min(n, p + t);
  o = min(o, p + u);
  p = min(p, p + v);
  q = min(q, p + w);
  r = min(r, p + x);
  s = min(s, v + s);
  t = min(t, v + t);
  u = min(u, v + u);
  v = min(v, v + v);
  w = min(w, v + w);
  x = min(x, v + x);
  y = min(y, B + s);
  z = min(z, B + t);
  A = min(A, B + u);
  B = min(B, B + v);
  C = min(C, B + w);
  D = min(D, B + x);
  E = min(E, H + s);
  F = min(F, H + t);
  G = min(G, H + u);
  H = min(H, H + v);
  I = min(I, H + w);
  J = min(J, H + x);
  a = min(a, e + y);
  b = min(b, e + z);
  c = min(c, e + A);
  d = min(d, e + B);
  e = min(e, e + C);
  f = min(f, e + D);
  g = min(g, k + y);
  h = min(h, k + z);
  i = min(i, k + A);
  j = min(j, k + B);
  k = min(k, k + C);
  l = min(l, k + D);
  m = min(m, q + y);
  n = min(n, q + z);
  o = min(o, q + A);
  p = min(p, q + B);
  q = min(q, q + C);
  r = min(r, q + D);
  s = min(s, w + y);
  t = min(t, w + z);
  u = min(u, w + A);
  v = min(v, w + B);
  w = min(w, w + C);
  x = min(x, w + D);
  y = min(y, C + y);
  z = min(z, C + z);
  A = min(A, C + A);
  B = min(B, C + B);
  C = min(C, C + C);
  D = min(D, C + D);
  E = min(E, I + y);
  F = min(F, I + z);
  G = min(G, I + A);
  H = min(H, I + B);
  I = min(I, I + C);
  J = min(J, I + D);
  a = min(a, f + E);
  b = min(b, f + F);
  c = min(c, f + G);
  d = min(d, f + H);
  e = min(e, f + I);
  f = min(f, f + J);
  g = min(g, l + E);
  h = min(h, l + F);
  i = min(i, l + G);
  j = min(j, l + H);
  k = min(k, l + I);
  l = min(l, l + J);
  m = min(m, r + E);
  n = min(n, r + F);
  o = min(o, r + G);
  p = min(p, r + H);
  q = min(q, r + I);
  r = min(r, r + J);
  s = min(s, x + E);
  t = min(t, x + F);
  u = min(u, x + G);
  v = min(v, x + H);
  w = min(w, x + I);
  x = min(x, x + J);
  y = min(y, D + E);
  z = min(z, D + F);
  A = min(A, D + G);
  B = min(B, D + H);
  C = min(C, D + I);
  D = min(D, D + J);
  E = min(E, J + E);
  F = min(F, J + F);
  G = min(G, J + G);
  H = min(H, J + H);
  I = min(I, J + I);
  J = min(J, J + J);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  _a = max(_a, e);
  _a = max(_a, f);
  _a = max(_a, g);
  _a = max(_a, h);
  _a = max(_a, i);
  _a = max(_a, j);
  _a = max(_a, k);
  _a = max(_a, l);
  _a = max(_a, m);
  _a = max(_a, n);
  _a = max(_a, o);
  _a = max(_a, p);
  _a = max(_a, q);
  _a = max(_a, r);
  _a = max(_a, s);
  _a = max(_a, t);
  _a = max(_a, u);
  _a = max(_a, v);
  _a = max(_a, w);
  _a = max(_a, x);
  _a = max(_a, y);
  _a = max(_a, z);
  _a = max(_a, A);
  _a = max(_a, B);
  _a = max(_a, C);
  _a = max(_a, D);
  _a = max(_a, E);
  _a = max(_a, F);
  _a = max(_a, G);
  _a = max(_a, H);
  _a = max(_a, I);
  _a = max(_a, J);
  printf("%d\n", _a);
}
void solve7() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, a + c);
  d = min(d, a + d);
  e = min(e, a + e);
  f = min(f, a + f);
  g = min(g, a + g);
  h = min(h, h + a);
  i = min(i, h + b);
  j = min(j, h + c);
  k = min(k, h + d);
  l = min(l, h + e);
  m = min(m, h + f);
  n = min(n, h + g);
  o = min(o, o + a);
  p = min(p, o + b);
  q = min(q, o + c);
  r = min(r, o + d);
  s = min(s, o + e);
  t = min(t, o + f);
  u = min(u, o + g);
  v = min(v, v + a);
  w = min(w, v + b);
  x = min(x, v + c);
  y = min(y, v + d);
  z = min(z, v + e);
  A = min(A, v + f);
  B = min(B, v + g);
  C = min(C, C + a);
  D = min(D, C + b);
  E = min(E, C + c);
  F = min(F, C + d);
  G = min(G, C + e);
  H = min(H, C + f);
  I = min(I, C + g);
  J = min(J, J + a);
  K = min(K, J + b);
  L = min(L, J + c);
  M = min(M, J + d);
  N = min(N, J + e);
  O = min(O, J + f);
  P = min(P, J + g);
  Q = min(Q, Q + a);
  R = min(R, Q + b);
  S = min(S, Q + c);
  T = min(T, Q + d);
  U = min(U, Q + e);
  V = min(V, Q + f);
  W = min(W, Q + g);
  a = min(a, b + h);
  b = min(b, b + i);
  c = min(c, b + j);
  d = min(d, b + k);
  e = min(e, b + l);
  f = min(f, b + m);
  g = min(g, b + n);
  h = min(h, i + h);
  i = min(i, i + i);
  j = min(j, i + j);
  k = min(k, i + k);
  l = min(l, i + l);
  m = min(m, i + m);
  n = min(n, i + n);
  o = min(o, p + h);
  p = min(p, p + i);
  q = min(q, p + j);
  r = min(r, p + k);
  s = min(s, p + l);
  t = min(t, p + m);
  u = min(u, p + n);
  v = min(v, w + h);
  w = min(w, w + i);
  x = min(x, w + j);
  y = min(y, w + k);
  z = min(z, w + l);
  A = min(A, w + m);
  B = min(B, w + n);
  C = min(C, D + h);
  D = min(D, D + i);
  E = min(E, D + j);
  F = min(F, D + k);
  G = min(G, D + l);
  H = min(H, D + m);
  I = min(I, D + n);
  J = min(J, K + h);
  K = min(K, K + i);
  L = min(L, K + j);
  M = min(M, K + k);
  N = min(N, K + l);
  O = min(O, K + m);
  P = min(P, K + n);
  Q = min(Q, R + h);
  R = min(R, R + i);
  S = min(S, R + j);
  T = min(T, R + k);
  U = min(U, R + l);
  V = min(V, R + m);
  W = min(W, R + n);
  a = min(a, c + o);
  b = min(b, c + p);
  c = min(c, c + q);
  d = min(d, c + r);
  e = min(e, c + s);
  f = min(f, c + t);
  g = min(g, c + u);
  h = min(h, j + o);
  i = min(i, j + p);
  j = min(j, j + q);
  k = min(k, j + r);
  l = min(l, j + s);
  m = min(m, j + t);
  n = min(n, j + u);
  o = min(o, q + o);
  p = min(p, q + p);
  q = min(q, q + q);
  r = min(r, q + r);
  s = min(s, q + s);
  t = min(t, q + t);
  u = min(u, q + u);
  v = min(v, x + o);
  w = min(w, x + p);
  x = min(x, x + q);
  y = min(y, x + r);
  z = min(z, x + s);
  A = min(A, x + t);
  B = min(B, x + u);
  C = min(C, E + o);
  D = min(D, E + p);
  E = min(E, E + q);
  F = min(F, E + r);
  G = min(G, E + s);
  H = min(H, E + t);
  I = min(I, E + u);
  J = min(J, L + o);
  K = min(K, L + p);
  L = min(L, L + q);
  M = min(M, L + r);
  N = min(N, L + s);
  O = min(O, L + t);
  P = min(P, L + u);
  Q = min(Q, S + o);
  R = min(R, S + p);
  S = min(S, S + q);
  T = min(T, S + r);
  U = min(U, S + s);
  V = min(V, S + t);
  W = min(W, S + u);
  a = min(a, d + v);
  b = min(b, d + w);
  c = min(c, d + x);
  d = min(d, d + y);
  e = min(e, d + z);
  f = min(f, d + A);
  g = min(g, d + B);
  h = min(h, k + v);
  i = min(i, k + w);
  j = min(j, k + x);
  k = min(k, k + y);
  l = min(l, k + z);
  m = min(m, k + A);
  n = min(n, k + B);
  o = min(o, r + v);
  p = min(p, r + w);
  q = min(q, r + x);
  r = min(r, r + y);
  s = min(s, r + z);
  t = min(t, r + A);
  u = min(u, r + B);
  v = min(v, y + v);
  w = min(w, y + w);
  x = min(x, y + x);
  y = min(y, y + y);
  z = min(z, y + z);
  A = min(A, y + A);
  B = min(B, y + B);
  C = min(C, F + v);
  D = min(D, F + w);
  E = min(E, F + x);
  F = min(F, F + y);
  G = min(G, F + z);
  H = min(H, F + A);
  I = min(I, F + B);
  J = min(J, M + v);
  K = min(K, M + w);
  L = min(L, M + x);
  M = min(M, M + y);
  N = min(N, M + z);
  O = min(O, M + A);
  P = min(P, M + B);
  Q = min(Q, T + v);
  R = min(R, T + w);
  S = min(S, T + x);
  T = min(T, T + y);
  U = min(U, T + z);
  V = min(V, T + A);
  W = min(W, T + B);
  a = min(a, e + C);
  b = min(b, e + D);
  c = min(c, e + E);
  d = min(d, e + F);
  e = min(e, e + G);
  f = min(f, e + H);
  g = min(g, e + I);
  h = min(h, l + C);
  i = min(i, l + D);
  j = min(j, l + E);
  k = min(k, l + F);
  l = min(l, l + G);
  m = min(m, l + H);
  n = min(n, l + I);
  o = min(o, s + C);
  p = min(p, s + D);
  q = min(q, s + E);
  r = min(r, s + F);
  s = min(s, s + G);
  t = min(t, s + H);
  u = min(u, s + I);
  v = min(v, z + C);
  w = min(w, z + D);
  x = min(x, z + E);
  y = min(y, z + F);
  z = min(z, z + G);
  A = min(A, z + H);
  B = min(B, z + I);
  C = min(C, G + C);
  D = min(D, G + D);
  E = min(E, G + E);
  F = min(F, G + F);
  G = min(G, G + G);
  H = min(H, G + H);
  I = min(I, G + I);
  J = min(J, N + C);
  K = min(K, N + D);
  L = min(L, N + E);
  M = min(M, N + F);
  N = min(N, N + G);
  O = min(O, N + H);
  P = min(P, N + I);
  Q = min(Q, U + C);
  R = min(R, U + D);
  S = min(S, U + E);
  T = min(T, U + F);
  U = min(U, U + G);
  V = min(V, U + H);
  W = min(W, U + I);
  a = min(a, f + J);
  b = min(b, f + K);
  c = min(c, f + L);
  d = min(d, f + M);
  e = min(e, f + N);
  f = min(f, f + O);
  g = min(g, f + P);
  h = min(h, m + J);
  i = min(i, m + K);
  j = min(j, m + L);
  k = min(k, m + M);
  l = min(l, m + N);
  m = min(m, m + O);
  n = min(n, m + P);
  o = min(o, t + J);
  p = min(p, t + K);
  q = min(q, t + L);
  r = min(r, t + M);
  s = min(s, t + N);
  t = min(t, t + O);
  u = min(u, t + P);
  v = min(v, A + J);
  w = min(w, A + K);
  x = min(x, A + L);
  y = min(y, A + M);
  z = min(z, A + N);
  A = min(A, A + O);
  B = min(B, A + P);
  C = min(C, H + J);
  D = min(D, H + K);
  E = min(E, H + L);
  F = min(F, H + M);
  G = min(G, H + N);
  H = min(H, H + O);
  I = min(I, H + P);
  J = min(J, O + J);
  K = min(K, O + K);
  L = min(L, O + L);
  M = min(M, O + M);
  N = min(N, O + N);
  O = min(O, O + O);
  P = min(P, O + P);
  Q = min(Q, V + J);
  R = min(R, V + K);
  S = min(S, V + L);
  T = min(T, V + M);
  U = min(U, V + N);
  V = min(V, V + O);
  W = min(W, V + P);
  a = min(a, g + Q);
  b = min(b, g + R);
  c = min(c, g + S);
  d = min(d, g + T);
  e = min(e, g + U);
  f = min(f, g + V);
  g = min(g, g + W);
  h = min(h, n + Q);
  i = min(i, n + R);
  j = min(j, n + S);
  k = min(k, n + T);
  l = min(l, n + U);
  m = min(m, n + V);
  n = min(n, n + W);
  o = min(o, u + Q);
  p = min(p, u + R);
  q = min(q, u + S);
  r = min(r, u + T);
  s = min(s, u + U);
  t = min(t, u + V);
  u = min(u, u + W);
  v = min(v, B + Q);
  w = min(w, B + R);
  x = min(x, B + S);
  y = min(y, B + T);
  z = min(z, B + U);
  A = min(A, B + V);
  B = min(B, B + W);
  C = min(C, I + Q);
  D = min(D, I + R);
  E = min(E, I + S);
  F = min(F, I + T);
  G = min(G, I + U);
  H = min(H, I + V);
  I = min(I, I + W);
  J = min(J, P + Q);
  K = min(K, P + R);
  L = min(L, P + S);
  M = min(M, P + T);
  N = min(N, P + U);
  O = min(O, P + V);
  P = min(P, P + W);
  Q = min(Q, W + Q);
  R = min(R, W + R);
  S = min(S, W + S);
  T = min(T, W + T);
  U = min(U, W + U);
  V = min(V, W + V);
  W = min(W, W + W);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  _a = max(_a, e);
  _a = max(_a, f);
  _a = max(_a, g);
  _a = max(_a, h);
  _a = max(_a, i);
  _a = max(_a, j);
  _a = max(_a, k);
  _a = max(_a, l);
  _a = max(_a, m);
  _a = max(_a, n);
  _a = max(_a, o);
  _a = max(_a, p);
  _a = max(_a, q);
  _a = max(_a, r);
  _a = max(_a, s);
  _a = max(_a, t);
  _a = max(_a, u);
  _a = max(_a, v);
  _a = max(_a, w);
  _a = max(_a, x);
  _a = max(_a, y);
  _a = max(_a, z);
  _a = max(_a, A);
  _a = max(_a, B);
  _a = max(_a, C);
  _a = max(_a, D);
  _a = max(_a, E);
  _a = max(_a, F);
  _a = max(_a, G);
  _a = max(_a, H);
  _a = max(_a, I);
  _a = max(_a, J);
  _a = max(_a, K);
  _a = max(_a, L);
  _a = max(_a, M);
  _a = max(_a, N);
  _a = max(_a, O);
  _a = max(_a, P);
  _a = max(_a, Q);
  _a = max(_a, R);
  _a = max(_a, S);
  _a = max(_a, T);
  _a = max(_a, U);
  _a = max(_a, V);
  _a = max(_a, W);
  printf("%d\n", _a);
}
void solve8() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, a + c);
  d = min(d, a + d);
  e = min(e, a + e);
  f = min(f, a + f);
  g = min(g, a + g);
  h = min(h, a + h);
  i = min(i, i + a);
  j = min(j, i + b);
  k = min(k, i + c);
  l = min(l, i + d);
  m = min(m, i + e);
  n = min(n, i + f);
  o = min(o, i + g);
  p = min(p, i + h);
  q = min(q, q + a);
  r = min(r, q + b);
  s = min(s, q + c);
  t = min(t, q + d);
  u = min(u, q + e);
  v = min(v, q + f);
  w = min(w, q + g);
  x = min(x, q + h);
  y = min(y, y + a);
  z = min(z, y + b);
  A = min(A, y + c);
  B = min(B, y + d);
  C = min(C, y + e);
  D = min(D, y + f);
  E = min(E, y + g);
  F = min(F, y + h);
  G = min(G, G + a);
  H = min(H, G + b);
  I = min(I, G + c);
  J = min(J, G + d);
  K = min(K, G + e);
  L = min(L, G + f);
  M = min(M, G + g);
  N = min(N, G + h);
  O = min(O, O + a);
  P = min(P, O + b);
  Q = min(Q, O + c);
  R = min(R, O + d);
  S = min(S, O + e);
  T = min(T, O + f);
  U = min(U, O + g);
  V = min(V, O + h);
  W = min(W, W + a);
  X = min(X, W + b);
  Y = min(Y, W + c);
  Z = min(Z, W + d);
  a5 = min(a5, W + e);
  b5 = min(b5, W + f);
  c5 = min(c5, W + g);
  d5 = min(d5, W + h);
  e5 = min(e5, e5 + a);
  f5 = min(f5, e5 + b);
  g5 = min(g5, e5 + c);
  h5 = min(h5, e5 + d);
  i5 = min(i5, e5 + e);
  j5 = min(j5, e5 + f);
  k5 = min(k5, e5 + g);
  l5 = min(l5, e5 + h);
  a = min(a, b + i);
  b = min(b, b + j);
  c = min(c, b + k);
  d = min(d, b + l);
  e = min(e, b + m);
  f = min(f, b + n);
  g = min(g, b + o);
  h = min(h, b + p);
  i = min(i, j + i);
  j = min(j, j + j);
  k = min(k, j + k);
  l = min(l, j + l);
  m = min(m, j + m);
  n = min(n, j + n);
  o = min(o, j + o);
  p = min(p, j + p);
  q = min(q, r + i);
  r = min(r, r + j);
  s = min(s, r + k);
  t = min(t, r + l);
  u = min(u, r + m);
  v = min(v, r + n);
  w = min(w, r + o);
  x = min(x, r + p);
  y = min(y, z + i);
  z = min(z, z + j);
  A = min(A, z + k);
  B = min(B, z + l);
  C = min(C, z + m);
  D = min(D, z + n);
  E = min(E, z + o);
  F = min(F, z + p);
  G = min(G, H + i);
  H = min(H, H + j);
  I = min(I, H + k);
  J = min(J, H + l);
  K = min(K, H + m);
  L = min(L, H + n);
  M = min(M, H + o);
  N = min(N, H + p);
  O = min(O, P + i);
  P = min(P, P + j);
  Q = min(Q, P + k);
  R = min(R, P + l);
  S = min(S, P + m);
  T = min(T, P + n);
  U = min(U, P + o);
  V = min(V, P + p);
  W = min(W, X + i);
  X = min(X, X + j);
  Y = min(Y, X + k);
  Z = min(Z, X + l);
  a5 = min(a5, X + m);
  b5 = min(b5, X + n);
  c5 = min(c5, X + o);
  d5 = min(d5, X + p);
  e5 = min(e5, f5 + i);
  f5 = min(f5, f5 + j);
  g5 = min(g5, f5 + k);
  h5 = min(h5, f5 + l);
  i5 = min(i5, f5 + m);
  j5 = min(j5, f5 + n);
  k5 = min(k5, f5 + o);
  l5 = min(l5, f5 + p);
  a = min(a, c + q);
  b = min(b, c + r);
  c = min(c, c + s);
  d = min(d, c + t);
  e = min(e, c + u);
  f = min(f, c + v);
  g = min(g, c + w);
  h = min(h, c + x);
  i = min(i, k + q);
  j = min(j, k + r);
  k = min(k, k + s);
  l = min(l, k + t);
  m = min(m, k + u);
  n = min(n, k + v);
  o = min(o, k + w);
  p = min(p, k + x);
  q = min(q, s + q);
  r = min(r, s + r);
  s = min(s, s + s);
  t = min(t, s + t);
  u = min(u, s + u);
  v = min(v, s + v);
  w = min(w, s + w);
  x = min(x, s + x);
  y = min(y, A + q);
  z = min(z, A + r);
  A = min(A, A + s);
  B = min(B, A + t);
  C = min(C, A + u);
  D = min(D, A + v);
  E = min(E, A + w);
  F = min(F, A + x);
  G = min(G, I + q);
  H = min(H, I + r);
  I = min(I, I + s);
  J = min(J, I + t);
  K = min(K, I + u);
  L = min(L, I + v);
  M = min(M, I + w);
  N = min(N, I + x);
  O = min(O, Q + q);
  P = min(P, Q + r);
  Q = min(Q, Q + s);
  R = min(R, Q + t);
  S = min(S, Q + u);
  T = min(T, Q + v);
  U = min(U, Q + w);
  V = min(V, Q + x);
  W = min(W, Y + q);
  X = min(X, Y + r);
  Y = min(Y, Y + s);
  Z = min(Z, Y + t);
  a5 = min(a5, Y + u);
  b5 = min(b5, Y + v);
  c5 = min(c5, Y + w);
  d5 = min(d5, Y + x);
  e5 = min(e5, g5 + q);
  f5 = min(f5, g5 + r);
  g5 = min(g5, g5 + s);
  h5 = min(h5, g5 + t);
  i5 = min(i5, g5 + u);
  j5 = min(j5, g5 + v);
  k5 = min(k5, g5 + w);
  l5 = min(l5, g5 + x);
  a = min(a, d + y);
  b = min(b, d + z);
  c = min(c, d + A);
  d = min(d, d + B);
  e = min(e, d + C);
  f = min(f, d + D);
  g = min(g, d + E);
  h = min(h, d + F);
  i = min(i, l + y);
  j = min(j, l + z);
  k = min(k, l + A);
  l = min(l, l + B);
  m = min(m, l + C);
  n = min(n, l + D);
  o = min(o, l + E);
  p = min(p, l + F);
  q = min(q, t + y);
  r = min(r, t + z);
  s = min(s, t + A);
  t = min(t, t + B);
  u = min(u, t + C);
  v = min(v, t + D);
  w = min(w, t + E);
  x = min(x, t + F);
  y = min(y, B + y);
  z = min(z, B + z);
  A = min(A, B + A);
  B = min(B, B + B);
  C = min(C, B + C);
  D = min(D, B + D);
  E = min(E, B + E);
  F = min(F, B + F);
  G = min(G, J + y);
  H = min(H, J + z);
  I = min(I, J + A);
  J = min(J, J + B);
  K = min(K, J + C);
  L = min(L, J + D);
  M = min(M, J + E);
  N = min(N, J + F);
  O = min(O, R + y);
  P = min(P, R + z);
  Q = min(Q, R + A);
  R = min(R, R + B);
  S = min(S, R + C);
  T = min(T, R + D);
  U = min(U, R + E);
  V = min(V, R + F);
  W = min(W, Z + y);
  X = min(X, Z + z);
  Y = min(Y, Z + A);
  Z = min(Z, Z + B);
  a5 = min(a5, Z + C);
  b5 = min(b5, Z + D);
  c5 = min(c5, Z + E);
  d5 = min(d5, Z + F);
  e5 = min(e5, h5 + y);
  f5 = min(f5, h5 + z);
  g5 = min(g5, h5 + A);
  h5 = min(h5, h5 + B);
  i5 = min(i5, h5 + C);
  j5 = min(j5, h5 + D);
  k5 = min(k5, h5 + E);
  l5 = min(l5, h5 + F);
  a = min(a, e + G);
  b = min(b, e + H);
  c = min(c, e + I);
  d = min(d, e + J);
  e = min(e, e + K);
  f = min(f, e + L);
  g = min(g, e + M);
  h = min(h, e + N);
  i = min(i, m + G);
  j = min(j, m + H);
  k = min(k, m + I);
  l = min(l, m + J);
  m = min(m, m + K);
  n = min(n, m + L);
  o = min(o, m + M);
  p = min(p, m + N);
  q = min(q, u + G);
  r = min(r, u + H);
  s = min(s, u + I);
  t = min(t, u + J);
  u = min(u, u + K);
  v = min(v, u + L);
  w = min(w, u + M);
  x = min(x, u + N);
  y = min(y, C + G);
  z = min(z, C + H);
  A = min(A, C + I);
  B = min(B, C + J);
  C = min(C, C + K);
  D = min(D, C + L);
  E = min(E, C + M);
  F = min(F, C + N);
  G = min(G, K + G);
  H = min(H, K + H);
  I = min(I, K + I);
  J = min(J, K + J);
  K = min(K, K + K);
  L = min(L, K + L);
  M = min(M, K + M);
  N = min(N, K + N);
  O = min(O, S + G);
  P = min(P, S + H);
  Q = min(Q, S + I);
  R = min(R, S + J);
  S = min(S, S + K);
  T = min(T, S + L);
  U = min(U, S + M);
  V = min(V, S + N);
  W = min(W, a5 + G);
  X = min(X, a5 + H);
  Y = min(Y, a5 + I);
  Z = min(Z, a5 + J);
  a5 = min(a5, a5 + K);
  b5 = min(b5, a5 + L);
  c5 = min(c5, a5 + M);
  d5 = min(d5, a5 + N);
  e5 = min(e5, i5 + G);
  f5 = min(f5, i5 + H);
  g5 = min(g5, i5 + I);
  h5 = min(h5, i5 + J);
  i5 = min(i5, i5 + K);
  j5 = min(j5, i5 + L);
  k5 = min(k5, i5 + M);
  l5 = min(l5, i5 + N);
  a = min(a, f + O);
  b = min(b, f + P);
  c = min(c, f + Q);
  d = min(d, f + R);
  e = min(e, f + S);
  f = min(f, f + T);
  g = min(g, f + U);
  h = min(h, f + V);
  i = min(i, n + O);
  j = min(j, n + P);
  k = min(k, n + Q);
  l = min(l, n + R);
  m = min(m, n + S);
  n = min(n, n + T);
  o = min(o, n + U);
  p = min(p, n + V);
  q = min(q, v + O);
  r = min(r, v + P);
  s = min(s, v + Q);
  t = min(t, v + R);
  u = min(u, v + S);
  v = min(v, v + T);
  w = min(w, v + U);
  x = min(x, v + V);
  y = min(y, D + O);
  z = min(z, D + P);
  A = min(A, D + Q);
  B = min(B, D + R);
  C = min(C, D + S);
  D = min(D, D + T);
  E = min(E, D + U);
  F = min(F, D + V);
  G = min(G, L + O);
  H = min(H, L + P);
  I = min(I, L + Q);
  J = min(J, L + R);
  K = min(K, L + S);
  L = min(L, L + T);
  M = min(M, L + U);
  N = min(N, L + V);
  O = min(O, T + O);
  P = min(P, T + P);
  Q = min(Q, T + Q);
  R = min(R, T + R);
  S = min(S, T + S);
  T = min(T, T + T);
  U = min(U, T + U);
  V = min(V, T + V);
  W = min(W, b5 + O);
  X = min(X, b5 + P);
  Y = min(Y, b5 + Q);
  Z = min(Z, b5 + R);
  a5 = min(a5, b5 + S);
  b5 = min(b5, b5 + T);
  c5 = min(c5, b5 + U);
  d5 = min(d5, b5 + V);
  e5 = min(e5, j5 + O);
  f5 = min(f5, j5 + P);
  g5 = min(g5, j5 + Q);
  h5 = min(h5, j5 + R);
  i5 = min(i5, j5 + S);
  j5 = min(j5, j5 + T);
  k5 = min(k5, j5 + U);
  l5 = min(l5, j5 + V);
  a = min(a, g + W);
  b = min(b, g + X);
  c = min(c, g + Y);
  d = min(d, g + Z);
  e = min(e, g + a5);
  f = min(f, g + b5);
  g = min(g, g + c5);
  h = min(h, g + d5);
  i = min(i, o + W);
  j = min(j, o + X);
  k = min(k, o + Y);
  l = min(l, o + Z);
  m = min(m, o + a5);
  n = min(n, o + b5);
  o = min(o, o + c5);
  p = min(p, o + d5);
  q = min(q, w + W);
  r = min(r, w + X);
  s = min(s, w + Y);
  t = min(t, w + Z);
  u = min(u, w + a5);
  v = min(v, w + b5);
  w = min(w, w + c5);
  x = min(x, w + d5);
  y = min(y, E + W);
  z = min(z, E + X);
  A = min(A, E + Y);
  B = min(B, E + Z);
  C = min(C, E + a5);
  D = min(D, E + b5);
  E = min(E, E + c5);
  F = min(F, E + d5);
  G = min(G, M + W);
  H = min(H, M + X);
  I = min(I, M + Y);
  J = min(J, M + Z);
  K = min(K, M + a5);
  L = min(L, M + b5);
  M = min(M, M + c5);
  N = min(N, M + d5);
  O = min(O, U + W);
  P = min(P, U + X);
  Q = min(Q, U + Y);
  R = min(R, U + Z);
  S = min(S, U + a5);
  T = min(T, U + b5);
  U = min(U, U + c5);
  V = min(V, U + d5);
  W = min(W, c5 + W);
  X = min(X, c5 + X);
  Y = min(Y, c5 + Y);
  Z = min(Z, c5 + Z);
  a5 = min(a5, c5 + a5);
  b5 = min(b5, c5 + b5);
  c5 = min(c5, c5 + c5);
  d5 = min(d5, c5 + d5);
  e5 = min(e5, k5 + W);
  f5 = min(f5, k5 + X);
  g5 = min(g5, k5 + Y);
  h5 = min(h5, k5 + Z);
  i5 = min(i5, k5 + a5);
  j5 = min(j5, k5 + b5);
  k5 = min(k5, k5 + c5);
  l5 = min(l5, k5 + d5);
  a = min(a, h + e5);
  b = min(b, h + f5);
  c = min(c, h + g5);
  d = min(d, h + h5);
  e = min(e, h + i5);
  f = min(f, h + j5);
  g = min(g, h + k5);
  h = min(h, h + l5);
  i = min(i, p + e5);
  j = min(j, p + f5);
  k = min(k, p + g5);
  l = min(l, p + h5);
  m = min(m, p + i5);
  n = min(n, p + j5);
  o = min(o, p + k5);
  p = min(p, p + l5);
  q = min(q, x + e5);
  r = min(r, x + f5);
  s = min(s, x + g5);
  t = min(t, x + h5);
  u = min(u, x + i5);
  v = min(v, x + j5);
  w = min(w, x + k5);
  x = min(x, x + l5);
  y = min(y, F + e5);
  z = min(z, F + f5);
  A = min(A, F + g5);
  B = min(B, F + h5);
  C = min(C, F + i5);
  D = min(D, F + j5);
  E = min(E, F + k5);
  F = min(F, F + l5);
  G = min(G, N + e5);
  H = min(H, N + f5);
  I = min(I, N + g5);
  J = min(J, N + h5);
  K = min(K, N + i5);
  L = min(L, N + j5);
  M = min(M, N + k5);
  N = min(N, N + l5);
  O = min(O, V + e5);
  P = min(P, V + f5);
  Q = min(Q, V + g5);
  R = min(R, V + h5);
  S = min(S, V + i5);
  T = min(T, V + j5);
  U = min(U, V + k5);
  V = min(V, V + l5);
  W = min(W, d5 + e5);
  X = min(X, d5 + f5);
  Y = min(Y, d5 + g5);
  Z = min(Z, d5 + h5);
  a5 = min(a5, d5 + i5);
  b5 = min(b5, d5 + j5);
  c5 = min(c5, d5 + k5);
  d5 = min(d5, d5 + l5);
  e5 = min(e5, l5 + e5);
  f5 = min(f5, l5 + f5);
  g5 = min(g5, l5 + g5);
  h5 = min(h5, l5 + h5);
  i5 = min(i5, l5 + i5);
  j5 = min(j5, l5 + j5);
  k5 = min(k5, l5 + k5);
  l5 = min(l5, l5 + l5);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  _a = max(_a, e);
  _a = max(_a, f);
  _a = max(_a, g);
  _a = max(_a, h);
  _a = max(_a, i);
  _a = max(_a, j);
  _a = max(_a, k);
  _a = max(_a, l);
  _a = max(_a, m);
  _a = max(_a, n);
  _a = max(_a, o);
  _a = max(_a, p);
  _a = max(_a, q);
  _a = max(_a, r);
  _a = max(_a, s);
  _a = max(_a, t);
  _a = max(_a, u);
  _a = max(_a, v);
  _a = max(_a, w);
  _a = max(_a, x);
  _a = max(_a, y);
  _a = max(_a, z);
  _a = max(_a, A);
  _a = max(_a, B);
  _a = max(_a, C);
  _a = max(_a, D);
  _a = max(_a, E);
  _a = max(_a, F);
  _a = max(_a, G);
  _a = max(_a, H);
  _a = max(_a, I);
  _a = max(_a, J);
  _a = max(_a, K);
  _a = max(_a, L);
  _a = max(_a, M);
  _a = max(_a, N);
  _a = max(_a, O);
  _a = max(_a, P);
  _a = max(_a, Q);
  _a = max(_a, R);
  _a = max(_a, S);
  _a = max(_a, T);
  _a = max(_a, U);
  _a = max(_a, V);
  _a = max(_a, W);
  _a = max(_a, X);
  _a = max(_a, Y);
  _a = max(_a, Z);
  _a = max(_a, a5);
  _a = max(_a, b5);
  _a = max(_a, c5);
  _a = max(_a, d5);
  _a = max(_a, e5);
  _a = max(_a, f5);
  _a = max(_a, g5);
  _a = max(_a, h5);
  _a = max(_a, i5);
  _a = max(_a, j5);
  _a = max(_a, k5);
  _a = max(_a, l5);
  printf("%d\n", _a);
}
void solve9() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, a + c);
  d = min(d, a + d);
  e = min(e, a + e);
  f = min(f, a + f);
  g = min(g, a + g);
  h = min(h, a + h);
  i = min(i, a + i);
  j = min(j, j + a);
  k = min(k, j + b);
  l = min(l, j + c);
  m = min(m, j + d);
  n = min(n, j + e);
  o = min(o, j + f);
  p = min(p, j + g);
  q = min(q, j + h);
  r = min(r, j + i);
  s = min(s, s + a);
  t = min(t, s + b);
  u = min(u, s + c);
  v = min(v, s + d);
  w = min(w, s + e);
  x = min(x, s + f);
  y = min(y, s + g);
  z = min(z, s + h);
  A = min(A, s + i);
  B = min(B, B + a);
  C = min(C, B + b);
  D = min(D, B + c);
  E = min(E, B + d);
  F = min(F, B + e);
  G = min(G, B + f);
  H = min(H, B + g);
  I = min(I, B + h);
  J = min(J, B + i);
  K = min(K, K + a);
  L = min(L, K + b);
  M = min(M, K + c);
  N = min(N, K + d);
  O = min(O, K + e);
  P = min(P, K + f);
  Q = min(Q, K + g);
  R = min(R, K + h);
  S = min(S, K + i);
  T = min(T, T + a);
  U = min(U, T + b);
  V = min(V, T + c);
  W = min(W, T + d);
  X = min(X, T + e);
  Y = min(Y, T + f);
  Z = min(Z, T + g);
  a5 = min(a5, T + h);
  b5 = min(b5, T + i);
  c5 = min(c5, c5 + a);
  d5 = min(d5, c5 + b);
  e5 = min(e5, c5 + c);
  f5 = min(f5, c5 + d);
  g5 = min(g5, c5 + e);
  h5 = min(h5, c5 + f);
  i5 = min(i5, c5 + g);
  j5 = min(j5, c5 + h);
  k5 = min(k5, c5 + i);
  l5 = min(l5, l5 + a);
  m5 = min(m5, l5 + b);
  n5 = min(n5, l5 + c);
  o5 = min(o5, l5 + d);
  p5 = min(p5, l5 + e);
  q5 = min(q5, l5 + f);
  r5 = min(r5, l5 + g);
  s5 = min(s5, l5 + h);
  t5 = min(t5, l5 + i);
  u5 = min(u5, u5 + a);
  v5 = min(v5, u5 + b);
  w5 = min(w5, u5 + c);
  x5 = min(x5, u5 + d);
  y5 = min(y5, u5 + e);
  z5 = min(z5, u5 + f);
  A5 = min(A5, u5 + g);
  B5 = min(B5, u5 + h);
  C5 = min(C5, u5 + i);
  a = min(a, b + j);
  b = min(b, b + k);
  c = min(c, b + l);
  d = min(d, b + m);
  e = min(e, b + n);
  f = min(f, b + o);
  g = min(g, b + p);
  h = min(h, b + q);
  i = min(i, b + r);
  j = min(j, k + j);
  k = min(k, k + k);
  l = min(l, k + l);
  m = min(m, k + m);
  n = min(n, k + n);
  o = min(o, k + o);
  p = min(p, k + p);
  q = min(q, k + q);
  r = min(r, k + r);
  s = min(s, t + j);
  t = min(t, t + k);
  u = min(u, t + l);
  v = min(v, t + m);
  w = min(w, t + n);
  x = min(x, t + o);
  y = min(y, t + p);
  z = min(z, t + q);
  A = min(A, t + r);
  B = min(B, C + j);
  C = min(C, C + k);
  D = min(D, C + l);
  E = min(E, C + m);
  F = min(F, C + n);
  G = min(G, C + o);
  H = min(H, C + p);
  I = min(I, C + q);
  J = min(J, C + r);
  K = min(K, L + j);
  L = min(L, L + k);
  M = min(M, L + l);
  N = min(N, L + m);
  O = min(O, L + n);
  P = min(P, L + o);
  Q = min(Q, L + p);
  R = min(R, L + q);
  S = min(S, L + r);
  T = min(T, U + j);
  U = min(U, U + k);
  V = min(V, U + l);
  W = min(W, U + m);
  X = min(X, U + n);
  Y = min(Y, U + o);
  Z = min(Z, U + p);
  a5 = min(a5, U + q);
  b5 = min(b5, U + r);
  c5 = min(c5, d5 + j);
  d5 = min(d5, d5 + k);
  e5 = min(e5, d5 + l);
  f5 = min(f5, d5 + m);
  g5 = min(g5, d5 + n);
  h5 = min(h5, d5 + o);
  i5 = min(i5, d5 + p);
  j5 = min(j5, d5 + q);
  k5 = min(k5, d5 + r);
  l5 = min(l5, m5 + j);
  m5 = min(m5, m5 + k);
  n5 = min(n5, m5 + l);
  o5 = min(o5, m5 + m);
  p5 = min(p5, m5 + n);
  q5 = min(q5, m5 + o);
  r5 = min(r5, m5 + p);
  s5 = min(s5, m5 + q);
  t5 = min(t5, m5 + r);
  u5 = min(u5, v5 + j);
  v5 = min(v5, v5 + k);
  w5 = min(w5, v5 + l);
  x5 = min(x5, v5 + m);
  y5 = min(y5, v5 + n);
  z5 = min(z5, v5 + o);
  A5 = min(A5, v5 + p);
  B5 = min(B5, v5 + q);
  C5 = min(C5, v5 + r);
  a = min(a, c + s);
  b = min(b, c + t);
  c = min(c, c + u);
  d = min(d, c + v);
  e = min(e, c + w);
  f = min(f, c + x);
  g = min(g, c + y);
  h = min(h, c + z);
  i = min(i, c + A);
  j = min(j, l + s);
  k = min(k, l + t);
  l = min(l, l + u);
  m = min(m, l + v);
  n = min(n, l + w);
  o = min(o, l + x);
  p = min(p, l + y);
  q = min(q, l + z);
  r = min(r, l + A);
  s = min(s, u + s);
  t = min(t, u + t);
  u = min(u, u + u);
  v = min(v, u + v);
  w = min(w, u + w);
  x = min(x, u + x);
  y = min(y, u + y);
  z = min(z, u + z);
  A = min(A, u + A);
  B = min(B, D + s);
  C = min(C, D + t);
  D = min(D, D + u);
  E = min(E, D + v);
  F = min(F, D + w);
  G = min(G, D + x);
  H = min(H, D + y);
  I = min(I, D + z);
  J = min(J, D + A);
  K = min(K, M + s);
  L = min(L, M + t);
  M = min(M, M + u);
  N = min(N, M + v);
  O = min(O, M + w);
  P = min(P, M + x);
  Q = min(Q, M + y);
  R = min(R, M + z);
  S = min(S, M + A);
  T = min(T, V + s);
  U = min(U, V + t);
  V = min(V, V + u);
  W = min(W, V + v);
  X = min(X, V + w);
  Y = min(Y, V + x);
  Z = min(Z, V + y);
  a5 = min(a5, V + z);
  b5 = min(b5, V + A);
  c5 = min(c5, e5 + s);
  d5 = min(d5, e5 + t);
  e5 = min(e5, e5 + u);
  f5 = min(f5, e5 + v);
  g5 = min(g5, e5 + w);
  h5 = min(h5, e5 + x);
  i5 = min(i5, e5 + y);
  j5 = min(j5, e5 + z);
  k5 = min(k5, e5 + A);
  l5 = min(l5, n5 + s);
  m5 = min(m5, n5 + t);
  n5 = min(n5, n5 + u);
  o5 = min(o5, n5 + v);
  p5 = min(p5, n5 + w);
  q5 = min(q5, n5 + x);
  r5 = min(r5, n5 + y);
  s5 = min(s5, n5 + z);
  t5 = min(t5, n5 + A);
  u5 = min(u5, w5 + s);
  v5 = min(v5, w5 + t);
  w5 = min(w5, w5 + u);
  x5 = min(x5, w5 + v);
  y5 = min(y5, w5 + w);
  z5 = min(z5, w5 + x);
  A5 = min(A5, w5 + y);
  B5 = min(B5, w5 + z);
  C5 = min(C5, w5 + A);
  a = min(a, d + B);
  b = min(b, d + C);
  c = min(c, d + D);
  d = min(d, d + E);
  e = min(e, d + F);
  f = min(f, d + G);
  g = min(g, d + H);
  h = min(h, d + I);
  i = min(i, d + J);
  j = min(j, m + B);
  k = min(k, m + C);
  l = min(l, m + D);
  m = min(m, m + E);
  n = min(n, m + F);
  o = min(o, m + G);
  p = min(p, m + H);
  q = min(q, m + I);
  r = min(r, m + J);
  s = min(s, v + B);
  t = min(t, v + C);
  u = min(u, v + D);
  v = min(v, v + E);
  w = min(w, v + F);
  x = min(x, v + G);
  y = min(y, v + H);
  z = min(z, v + I);
  A = min(A, v + J);
  B = min(B, E + B);
  C = min(C, E + C);
  D = min(D, E + D);
  E = min(E, E + E);
  F = min(F, E + F);
  G = min(G, E + G);
  H = min(H, E + H);
  I = min(I, E + I);
  J = min(J, E + J);
  K = min(K, N + B);
  L = min(L, N + C);
  M = min(M, N + D);
  N = min(N, N + E);
  O = min(O, N + F);
  P = min(P, N + G);
  Q = min(Q, N + H);
  R = min(R, N + I);
  S = min(S, N + J);
  T = min(T, W + B);
  U = min(U, W + C);
  V = min(V, W + D);
  W = min(W, W + E);
  X = min(X, W + F);
  Y = min(Y, W + G);
  Z = min(Z, W + H);
  a5 = min(a5, W + I);
  b5 = min(b5, W + J);
  c5 = min(c5, f5 + B);
  d5 = min(d5, f5 + C);
  e5 = min(e5, f5 + D);
  f5 = min(f5, f5 + E);
  g5 = min(g5, f5 + F);
  h5 = min(h5, f5 + G);
  i5 = min(i5, f5 + H);
  j5 = min(j5, f5 + I);
  k5 = min(k5, f5 + J);
  l5 = min(l5, o5 + B);
  m5 = min(m5, o5 + C);
  n5 = min(n5, o5 + D);
  o5 = min(o5, o5 + E);
  p5 = min(p5, o5 + F);
  q5 = min(q5, o5 + G);
  r5 = min(r5, o5 + H);
  s5 = min(s5, o5 + I);
  t5 = min(t5, o5 + J);
  u5 = min(u5, x5 + B);
  v5 = min(v5, x5 + C);
  w5 = min(w5, x5 + D);
  x5 = min(x5, x5 + E);
  y5 = min(y5, x5 + F);
  z5 = min(z5, x5 + G);
  A5 = min(A5, x5 + H);
  B5 = min(B5, x5 + I);
  C5 = min(C5, x5 + J);
  a = min(a, e + K);
  b = min(b, e + L);
  c = min(c, e + M);
  d = min(d, e + N);
  e = min(e, e + O);
  f = min(f, e + P);
  g = min(g, e + Q);
  h = min(h, e + R);
  i = min(i, e + S);
  j = min(j, n + K);
  k = min(k, n + L);
  l = min(l, n + M);
  m = min(m, n + N);
  n = min(n, n + O);
  o = min(o, n + P);
  p = min(p, n + Q);
  q = min(q, n + R);
  r = min(r, n + S);
  s = min(s, w + K);
  t = min(t, w + L);
  u = min(u, w + M);
  v = min(v, w + N);
  w = min(w, w + O);
  x = min(x, w + P);
  y = min(y, w + Q);
  z = min(z, w + R);
  A = min(A, w + S);
  B = min(B, F + K);
  C = min(C, F + L);
  D = min(D, F + M);
  E = min(E, F + N);
  F = min(F, F + O);
  G = min(G, F + P);
  H = min(H, F + Q);
  I = min(I, F + R);
  J = min(J, F + S);
  K = min(K, O + K);
  L = min(L, O + L);
  M = min(M, O + M);
  N = min(N, O + N);
  O = min(O, O + O);
  P = min(P, O + P);
  Q = min(Q, O + Q);
  R = min(R, O + R);
  S = min(S, O + S);
  T = min(T, X + K);
  U = min(U, X + L);
  V = min(V, X + M);
  W = min(W, X + N);
  X = min(X, X + O);
  Y = min(Y, X + P);
  Z = min(Z, X + Q);
  a5 = min(a5, X + R);
  b5 = min(b5, X + S);
  c5 = min(c5, g5 + K);
  d5 = min(d5, g5 + L);
  e5 = min(e5, g5 + M);
  f5 = min(f5, g5 + N);
  g5 = min(g5, g5 + O);
  h5 = min(h5, g5 + P);
  i5 = min(i5, g5 + Q);
  j5 = min(j5, g5 + R);
  k5 = min(k5, g5 + S);
  l5 = min(l5, p5 + K);
  m5 = min(m5, p5 + L);
  n5 = min(n5, p5 + M);
  o5 = min(o5, p5 + N);
  p5 = min(p5, p5 + O);
  q5 = min(q5, p5 + P);
  r5 = min(r5, p5 + Q);
  s5 = min(s5, p5 + R);
  t5 = min(t5, p5 + S);
  u5 = min(u5, y5 + K);
  v5 = min(v5, y5 + L);
  w5 = min(w5, y5 + M);
  x5 = min(x5, y5 + N);
  y5 = min(y5, y5 + O);
  z5 = min(z5, y5 + P);
  A5 = min(A5, y5 + Q);
  B5 = min(B5, y5 + R);
  C5 = min(C5, y5 + S);
  a = min(a, f + T);
  b = min(b, f + U);
  c = min(c, f + V);
  d = min(d, f + W);
  e = min(e, f + X);
  f = min(f, f + Y);
  g = min(g, f + Z);
  h = min(h, f + a5);
  i = min(i, f + b5);
  j = min(j, o + T);
  k = min(k, o + U);
  l = min(l, o + V);
  m = min(m, o + W);
  n = min(n, o + X);
  o = min(o, o + Y);
  p = min(p, o + Z);
  q = min(q, o + a5);
  r = min(r, o + b5);
  s = min(s, x + T);
  t = min(t, x + U);
  u = min(u, x + V);
  v = min(v, x + W);
  w = min(w, x + X);
  x = min(x, x + Y);
  y = min(y, x + Z);
  z = min(z, x + a5);
  A = min(A, x + b5);
  B = min(B, G + T);
  C = min(C, G + U);
  D = min(D, G + V);
  E = min(E, G + W);
  F = min(F, G + X);
  G = min(G, G + Y);
  H = min(H, G + Z);
  I = min(I, G + a5);
  J = min(J, G + b5);
  K = min(K, P + T);
  L = min(L, P + U);
  M = min(M, P + V);
  N = min(N, P + W);
  O = min(O, P + X);
  P = min(P, P + Y);
  Q = min(Q, P + Z);
  R = min(R, P + a5);
  S = min(S, P + b5);
  T = min(T, Y + T);
  U = min(U, Y + U);
  V = min(V, Y + V);
  W = min(W, Y + W);
  X = min(X, Y + X);
  Y = min(Y, Y + Y);
  Z = min(Z, Y + Z);
  a5 = min(a5, Y + a5);
  b5 = min(b5, Y + b5);
  c5 = min(c5, h5 + T);
  d5 = min(d5, h5 + U);
  e5 = min(e5, h5 + V);
  f5 = min(f5, h5 + W);
  g5 = min(g5, h5 + X);
  h5 = min(h5, h5 + Y);
  i5 = min(i5, h5 + Z);
  j5 = min(j5, h5 + a5);
  k5 = min(k5, h5 + b5);
  l5 = min(l5, q5 + T);
  m5 = min(m5, q5 + U);
  n5 = min(n5, q5 + V);
  o5 = min(o5, q5 + W);
  p5 = min(p5, q5 + X);
  q5 = min(q5, q5 + Y);
  r5 = min(r5, q5 + Z);
  s5 = min(s5, q5 + a5);
  t5 = min(t5, q5 + b5);
  u5 = min(u5, z5 + T);
  v5 = min(v5, z5 + U);
  w5 = min(w5, z5 + V);
  x5 = min(x5, z5 + W);
  y5 = min(y5, z5 + X);
  z5 = min(z5, z5 + Y);
  A5 = min(A5, z5 + Z);
  B5 = min(B5, z5 + a5);
  C5 = min(C5, z5 + b5);
  a = min(a, g + c5);
  b = min(b, g + d5);
  c = min(c, g + e5);
  d = min(d, g + f5);
  e = min(e, g + g5);
  f = min(f, g + h5);
  g = min(g, g + i5);
  h = min(h, g + j5);
  i = min(i, g + k5);
  j = min(j, p + c5);
  k = min(k, p + d5);
  l = min(l, p + e5);
  m = min(m, p + f5);
  n = min(n, p + g5);
  o = min(o, p + h5);
  p = min(p, p + i5);
  q = min(q, p + j5);
  r = min(r, p + k5);
  s = min(s, y + c5);
  t = min(t, y + d5);
  u = min(u, y + e5);
  v = min(v, y + f5);
  w = min(w, y + g5);
  x = min(x, y + h5);
  y = min(y, y + i5);
  z = min(z, y + j5);
  A = min(A, y + k5);
  B = min(B, H + c5);
  C = min(C, H + d5);
  D = min(D, H + e5);
  E = min(E, H + f5);
  F = min(F, H + g5);
  G = min(G, H + h5);
  H = min(H, H + i5);
  I = min(I, H + j5);
  J = min(J, H + k5);
  K = min(K, Q + c5);
  L = min(L, Q + d5);
  M = min(M, Q + e5);
  N = min(N, Q + f5);
  O = min(O, Q + g5);
  P = min(P, Q + h5);
  Q = min(Q, Q + i5);
  R = min(R, Q + j5);
  S = min(S, Q + k5);
  T = min(T, Z + c5);
  U = min(U, Z + d5);
  V = min(V, Z + e5);
  W = min(W, Z + f5);
  X = min(X, Z + g5);
  Y = min(Y, Z + h5);
  Z = min(Z, Z + i5);
  a5 = min(a5, Z + j5);
  b5 = min(b5, Z + k5);
  c5 = min(c5, i5 + c5);
  d5 = min(d5, i5 + d5);
  e5 = min(e5, i5 + e5);
  f5 = min(f5, i5 + f5);
  g5 = min(g5, i5 + g5);
  h5 = min(h5, i5 + h5);
  i5 = min(i5, i5 + i5);
  j5 = min(j5, i5 + j5);
  k5 = min(k5, i5 + k5);
  l5 = min(l5, r5 + c5);
  m5 = min(m5, r5 + d5);
  n5 = min(n5, r5 + e5);
  o5 = min(o5, r5 + f5);
  p5 = min(p5, r5 + g5);
  q5 = min(q5, r5 + h5);
  r5 = min(r5, r5 + i5);
  s5 = min(s5, r5 + j5);
  t5 = min(t5, r5 + k5);
  u5 = min(u5, A5 + c5);
  v5 = min(v5, A5 + d5);
  w5 = min(w5, A5 + e5);
  x5 = min(x5, A5 + f5);
  y5 = min(y5, A5 + g5);
  z5 = min(z5, A5 + h5);
  A5 = min(A5, A5 + i5);
  B5 = min(B5, A5 + j5);
  C5 = min(C5, A5 + k5);
  a = min(a, h + l5);
  b = min(b, h + m5);
  c = min(c, h + n5);
  d = min(d, h + o5);
  e = min(e, h + p5);
  f = min(f, h + q5);
  g = min(g, h + r5);
  h = min(h, h + s5);
  i = min(i, h + t5);
  j = min(j, q + l5);
  k = min(k, q + m5);
  l = min(l, q + n5);
  m = min(m, q + o5);
  n = min(n, q + p5);
  o = min(o, q + q5);
  p = min(p, q + r5);
  q = min(q, q + s5);
  r = min(r, q + t5);
  s = min(s, z + l5);
  t = min(t, z + m5);
  u = min(u, z + n5);
  v = min(v, z + o5);
  w = min(w, z + p5);
  x = min(x, z + q5);
  y = min(y, z + r5);
  z = min(z, z + s5);
  A = min(A, z + t5);
  B = min(B, I + l5);
  C = min(C, I + m5);
  D = min(D, I + n5);
  E = min(E, I + o5);
  F = min(F, I + p5);
  G = min(G, I + q5);
  H = min(H, I + r5);
  I = min(I, I + s5);
  J = min(J, I + t5);
  K = min(K, R + l5);
  L = min(L, R + m5);
  M = min(M, R + n5);
  N = min(N, R + o5);
  O = min(O, R + p5);
  P = min(P, R + q5);
  Q = min(Q, R + r5);
  R = min(R, R + s5);
  S = min(S, R + t5);
  T = min(T, a5 + l5);
  U = min(U, a5 + m5);
  V = min(V, a5 + n5);
  W = min(W, a5 + o5);
  X = min(X, a5 + p5);
  Y = min(Y, a5 + q5);
  Z = min(Z, a5 + r5);
  a5 = min(a5, a5 + s5);
  b5 = min(b5, a5 + t5);
  c5 = min(c5, j5 + l5);
  d5 = min(d5, j5 + m5);
  e5 = min(e5, j5 + n5);
  f5 = min(f5, j5 + o5);
  g5 = min(g5, j5 + p5);
  h5 = min(h5, j5 + q5);
  i5 = min(i5, j5 + r5);
  j5 = min(j5, j5 + s5);
  k5 = min(k5, j5 + t5);
  l5 = min(l5, s5 + l5);
  m5 = min(m5, s5 + m5);
  n5 = min(n5, s5 + n5);
  o5 = min(o5, s5 + o5);
  p5 = min(p5, s5 + p5);
  q5 = min(q5, s5 + q5);
  r5 = min(r5, s5 + r5);
  s5 = min(s5, s5 + s5);
  t5 = min(t5, s5 + t5);
  u5 = min(u5, B5 + l5);
  v5 = min(v5, B5 + m5);
  w5 = min(w5, B5 + n5);
  x5 = min(x5, B5 + o5);
  y5 = min(y5, B5 + p5);
  z5 = min(z5, B5 + q5);
  A5 = min(A5, B5 + r5);
  B5 = min(B5, B5 + s5);
  C5 = min(C5, B5 + t5);
  a = min(a, i + u5);
  b = min(b, i + v5);
  c = min(c, i + w5);
  d = min(d, i + x5);
  e = min(e, i + y5);
  f = min(f, i + z5);
  g = min(g, i + A5);
  h = min(h, i + B5);
  i = min(i, i + C5);
  j = min(j, r + u5);
  k = min(k, r + v5);
  l = min(l, r + w5);
  m = min(m, r + x5);
  n = min(n, r + y5);
  o = min(o, r + z5);
  p = min(p, r + A5);
  q = min(q, r + B5);
  r = min(r, r + C5);
  s = min(s, A + u5);
  t = min(t, A + v5);
  u = min(u, A + w5);
  v = min(v, A + x5);
  w = min(w, A + y5);
  x = min(x, A + z5);
  y = min(y, A + A5);
  z = min(z, A + B5);
  A = min(A, A + C5);
  B = min(B, J + u5);
  C = min(C, J + v5);
  D = min(D, J + w5);
  E = min(E, J + x5);
  F = min(F, J + y5);
  G = min(G, J + z5);
  H = min(H, J + A5);
  I = min(I, J + B5);
  J = min(J, J + C5);
  K = min(K, S + u5);
  L = min(L, S + v5);
  M = min(M, S + w5);
  N = min(N, S + x5);
  O = min(O, S + y5);
  P = min(P, S + z5);
  Q = min(Q, S + A5);
  R = min(R, S + B5);
  S = min(S, S + C5);
  T = min(T, b5 + u5);
  U = min(U, b5 + v5);
  V = min(V, b5 + w5);
  W = min(W, b5 + x5);
  X = min(X, b5 + y5);
  Y = min(Y, b5 + z5);
  Z = min(Z, b5 + A5);
  a5 = min(a5, b5 + B5);
  b5 = min(b5, b5 + C5);
  c5 = min(c5, k5 + u5);
  d5 = min(d5, k5 + v5);
  e5 = min(e5, k5 + w5);
  f5 = min(f5, k5 + x5);
  g5 = min(g5, k5 + y5);
  h5 = min(h5, k5 + z5);
  i5 = min(i5, k5 + A5);
  j5 = min(j5, k5 + B5);
  k5 = min(k5, k5 + C5);
  l5 = min(l5, t5 + u5);
  m5 = min(m5, t5 + v5);
  n5 = min(n5, t5 + w5);
  o5 = min(o5, t5 + x5);
  p5 = min(p5, t5 + y5);
  q5 = min(q5, t5 + z5);
  r5 = min(r5, t5 + A5);
  s5 = min(s5, t5 + B5);
  t5 = min(t5, t5 + C5);
  u5 = min(u5, C5 + u5);
  v5 = min(v5, C5 + v5);
  w5 = min(w5, C5 + w5);
  x5 = min(x5, C5 + x5);
  y5 = min(y5, C5 + y5);
  z5 = min(z5, C5 + z5);
  A5 = min(A5, C5 + A5);
  B5 = min(B5, C5 + B5);
  C5 = min(C5, C5 + C5);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  _a = max(_a, e);
  _a = max(_a, f);
  _a = max(_a, g);
  _a = max(_a, h);
  _a = max(_a, i);
  _a = max(_a, j);
  _a = max(_a, k);
  _a = max(_a, l);
  _a = max(_a, m);
  _a = max(_a, n);
  _a = max(_a, o);
  _a = max(_a, p);
  _a = max(_a, q);
  _a = max(_a, r);
  _a = max(_a, s);
  _a = max(_a, t);
  _a = max(_a, u);
  _a = max(_a, v);
  _a = max(_a, w);
  _a = max(_a, x);
  _a = max(_a, y);
  _a = max(_a, z);
  _a = max(_a, A);
  _a = max(_a, B);
  _a = max(_a, C);
  _a = max(_a, D);
  _a = max(_a, E);
  _a = max(_a, F);
  _a = max(_a, G);
  _a = max(_a, H);
  _a = max(_a, I);
  _a = max(_a, J);
  _a = max(_a, K);
  _a = max(_a, L);
  _a = max(_a, M);
  _a = max(_a, N);
  _a = max(_a, O);
  _a = max(_a, P);
  _a = max(_a, Q);
  _a = max(_a, R);
  _a = max(_a, S);
  _a = max(_a, T);
  _a = max(_a, U);
  _a = max(_a, V);
  _a = max(_a, W);
  _a = max(_a, X);
  _a = max(_a, Y);
  _a = max(_a, Z);
  _a = max(_a, a5);
  _a = max(_a, b5);
  _a = max(_a, c5);
  _a = max(_a, d5);
  _a = max(_a, e5);
  _a = max(_a, f5);
  _a = max(_a, g5);
  _a = max(_a, h5);
  _a = max(_a, i5);
  _a = max(_a, j5);
  _a = max(_a, k5);
  _a = max(_a, l5);
  _a = max(_a, m5);
  _a = max(_a, n5);
  _a = max(_a, o5);
  _a = max(_a, p5);
  _a = max(_a, q5);
  _a = max(_a, r5);
  _a = max(_a, s5);
  _a = max(_a, t5);
  _a = max(_a, u5);
  _a = max(_a, v5);
  _a = max(_a, w5);
  _a = max(_a, x5);
  _a = max(_a, y5);
  _a = max(_a, z5);
  _a = max(_a, A5);
  _a = max(_a, B5);
  _a = max(_a, C5);
  printf("%d\n", _a);
}
void solve10() {
  a = min(a, a + a);
  b = min(b, a + b);
  c = min(c, a + c);
  d = min(d, a + d);
  e = min(e, a + e);
  f = min(f, a + f);
  g = min(g, a + g);
  h = min(h, a + h);
  i = min(i, a + i);
  j = min(j, a + j);
  k = min(k, k + a);
  l = min(l, k + b);
  m = min(m, k + c);
  n = min(n, k + d);
  o = min(o, k + e);
  p = min(p, k + f);
  q = min(q, k + g);
  r = min(r, k + h);
  s = min(s, k + i);
  t = min(t, k + j);
  u = min(u, u + a);
  v = min(v, u + b);
  w = min(w, u + c);
  x = min(x, u + d);
  y = min(y, u + e);
  z = min(z, u + f);
  A = min(A, u + g);
  B = min(B, u + h);
  C = min(C, u + i);
  D = min(D, u + j);
  E = min(E, E + a);
  F = min(F, E + b);
  G = min(G, E + c);
  H = min(H, E + d);
  I = min(I, E + e);
  J = min(J, E + f);
  K = min(K, E + g);
  L = min(L, E + h);
  M = min(M, E + i);
  N = min(N, E + j);
  O = min(O, O + a);
  P = min(P, O + b);
  Q = min(Q, O + c);
  R = min(R, O + d);
  S = min(S, O + e);
  T = min(T, O + f);
  U = min(U, O + g);
  V = min(V, O + h);
  W = min(W, O + i);
  X = min(X, O + j);
  Y = min(Y, Y + a);
  Z = min(Z, Y + b);
  a5 = min(a5, Y + c);
  b5 = min(b5, Y + d);
  c5 = min(c5, Y + e);
  d5 = min(d5, Y + f);
  e5 = min(e5, Y + g);
  f5 = min(f5, Y + h);
  g5 = min(g5, Y + i);
  h5 = min(h5, Y + j);
  i5 = min(i5, i5 + a);
  j5 = min(j5, i5 + b);
  k5 = min(k5, i5 + c);
  l5 = min(l5, i5 + d);
  m5 = min(m5, i5 + e);
  n5 = min(n5, i5 + f);
  o5 = min(o5, i5 + g);
  p5 = min(p5, i5 + h);
  q5 = min(q5, i5 + i);
  r5 = min(r5, i5 + j);
  s5 = min(s5, s5 + a);
  t5 = min(t5, s5 + b);
  u5 = min(u5, s5 + c);
  v5 = min(v5, s5 + d);
  w5 = min(w5, s5 + e);
  x5 = min(x5, s5 + f);
  y5 = min(y5, s5 + g);
  z5 = min(z5, s5 + h);
  A5 = min(A5, s5 + i);
  B5 = min(B5, s5 + j);
  C5 = min(C5, C5 + a);
  D5 = min(D5, C5 + b);
  E5 = min(E5, C5 + c);
  F5 = min(F5, C5 + d);
  G5 = min(G5, C5 + e);
  H5 = min(H5, C5 + f);
  I5 = min(I5, C5 + g);
  J5 = min(J5, C5 + h);
  K5 = min(K5, C5 + i);
  L5 = min(L5, C5 + j);
  M5 = min(M5, M5 + a);
  N5 = min(N5, M5 + b);
  O5 = min(O5, M5 + c);
  P5 = min(P5, M5 + d);
  Q5 = min(Q5, M5 + e);
  R5 = min(R5, M5 + f);
  S5 = min(S5, M5 + g);
  T5 = min(T5, M5 + h);
  U5 = min(U5, M5 + i);
  V5 = min(V5, M5 + j);
  a = min(a, b + k);
  b = min(b, b + l);
  c = min(c, b + m);
  d = min(d, b + n);
  e = min(e, b + o);
  f = min(f, b + p);
  g = min(g, b + q);
  h = min(h, b + r);
  i = min(i, b + s);
  j = min(j, b + t);
  k = min(k, l + k);
  l = min(l, l + l);
  m = min(m, l + m);
  n = min(n, l + n);
  o = min(o, l + o);
  p = min(p, l + p);
  q = min(q, l + q);
  r = min(r, l + r);
  s = min(s, l + s);
  t = min(t, l + t);
  u = min(u, v + k);
  v = min(v, v + l);
  w = min(w, v + m);
  x = min(x, v + n);
  y = min(y, v + o);
  z = min(z, v + p);
  A = min(A, v + q);
  B = min(B, v + r);
  C = min(C, v + s);
  D = min(D, v + t);
  E = min(E, F + k);
  F = min(F, F + l);
  G = min(G, F + m);
  H = min(H, F + n);
  I = min(I, F + o);
  J = min(J, F + p);
  K = min(K, F + q);
  L = min(L, F + r);
  M = min(M, F + s);
  N = min(N, F + t);
  O = min(O, P + k);
  P = min(P, P + l);
  Q = min(Q, P + m);
  R = min(R, P + n);
  S = min(S, P + o);
  T = min(T, P + p);
  U = min(U, P + q);
  V = min(V, P + r);
  W = min(W, P + s);
  X = min(X, P + t);
  Y = min(Y, Z + k);
  Z = min(Z, Z + l);
  a5 = min(a5, Z + m);
  b5 = min(b5, Z + n);
  c5 = min(c5, Z + o);
  d5 = min(d5, Z + p);
  e5 = min(e5, Z + q);
  f5 = min(f5, Z + r);
  g5 = min(g5, Z + s);
  h5 = min(h5, Z + t);
  i5 = min(i5, j5 + k);
  j5 = min(j5, j5 + l);
  k5 = min(k5, j5 + m);
  l5 = min(l5, j5 + n);
  m5 = min(m5, j5 + o);
  n5 = min(n5, j5 + p);
  o5 = min(o5, j5 + q);
  p5 = min(p5, j5 + r);
  q5 = min(q5, j5 + s);
  r5 = min(r5, j5 + t);
  s5 = min(s5, t5 + k);
  t5 = min(t5, t5 + l);
  u5 = min(u5, t5 + m);
  v5 = min(v5, t5 + n);
  w5 = min(w5, t5 + o);
  x5 = min(x5, t5 + p);
  y5 = min(y5, t5 + q);
  z5 = min(z5, t5 + r);
  A5 = min(A5, t5 + s);
  B5 = min(B5, t5 + t);
  C5 = min(C5, D5 + k);
  D5 = min(D5, D5 + l);
  E5 = min(E5, D5 + m);
  F5 = min(F5, D5 + n);
  G5 = min(G5, D5 + o);
  H5 = min(H5, D5 + p);
  I5 = min(I5, D5 + q);
  J5 = min(J5, D5 + r);
  K5 = min(K5, D5 + s);
  L5 = min(L5, D5 + t);
  M5 = min(M5, N5 + k);
  N5 = min(N5, N5 + l);
  O5 = min(O5, N5 + m);
  P5 = min(P5, N5 + n);
  Q5 = min(Q5, N5 + o);
  R5 = min(R5, N5 + p);
  S5 = min(S5, N5 + q);
  T5 = min(T5, N5 + r);
  U5 = min(U5, N5 + s);
  V5 = min(V5, N5 + t);
  a = min(a, c + u);
  b = min(b, c + v);
  c = min(c, c + w);
  d = min(d, c + x);
  e = min(e, c + y);
  f = min(f, c + z);
  g = min(g, c + A);
  h = min(h, c + B);
  i = min(i, c + C);
  j = min(j, c + D);
  k = min(k, m + u);
  l = min(l, m + v);
  m = min(m, m + w);
  n = min(n, m + x);
  o = min(o, m + y);
  p = min(p, m + z);
  q = min(q, m + A);
  r = min(r, m + B);
  s = min(s, m + C);
  t = min(t, m + D);
  u = min(u, w + u);
  v = min(v, w + v);
  w = min(w, w + w);
  x = min(x, w + x);
  y = min(y, w + y);
  z = min(z, w + z);
  A = min(A, w + A);
  B = min(B, w + B);
  C = min(C, w + C);
  D = min(D, w + D);
  E = min(E, G + u);
  F = min(F, G + v);
  G = min(G, G + w);
  H = min(H, G + x);
  I = min(I, G + y);
  J = min(J, G + z);
  K = min(K, G + A);
  L = min(L, G + B);
  M = min(M, G + C);
  N = min(N, G + D);
  O = min(O, Q + u);
  P = min(P, Q + v);
  Q = min(Q, Q + w);
  R = min(R, Q + x);
  S = min(S, Q + y);
  T = min(T, Q + z);
  U = min(U, Q + A);
  V = min(V, Q + B);
  W = min(W, Q + C);
  X = min(X, Q + D);
  Y = min(Y, a5 + u);
  Z = min(Z, a5 + v);
  a5 = min(a5, a5 + w);
  b5 = min(b5, a5 + x);
  c5 = min(c5, a5 + y);
  d5 = min(d5, a5 + z);
  e5 = min(e5, a5 + A);
  f5 = min(f5, a5 + B);
  g5 = min(g5, a5 + C);
  h5 = min(h5, a5 + D);
  i5 = min(i5, k5 + u);
  j5 = min(j5, k5 + v);
  k5 = min(k5, k5 + w);
  l5 = min(l5, k5 + x);
  m5 = min(m5, k5 + y);
  n5 = min(n5, k5 + z);
  o5 = min(o5, k5 + A);
  p5 = min(p5, k5 + B);
  q5 = min(q5, k5 + C);
  r5 = min(r5, k5 + D);
  s5 = min(s5, u5 + u);
  t5 = min(t5, u5 + v);
  u5 = min(u5, u5 + w);
  v5 = min(v5, u5 + x);
  w5 = min(w5, u5 + y);
  x5 = min(x5, u5 + z);
  y5 = min(y5, u5 + A);
  z5 = min(z5, u5 + B);
  A5 = min(A5, u5 + C);
  B5 = min(B5, u5 + D);
  C5 = min(C5, E5 + u);
  D5 = min(D5, E5 + v);
  E5 = min(E5, E5 + w);
  F5 = min(F5, E5 + x);
  G5 = min(G5, E5 + y);
  H5 = min(H5, E5 + z);
  I5 = min(I5, E5 + A);
  J5 = min(J5, E5 + B);
  K5 = min(K5, E5 + C);
  L5 = min(L5, E5 + D);
  M5 = min(M5, O5 + u);
  N5 = min(N5, O5 + v);
  O5 = min(O5, O5 + w);
  P5 = min(P5, O5 + x);
  Q5 = min(Q5, O5 + y);
  R5 = min(R5, O5 + z);
  S5 = min(S5, O5 + A);
  T5 = min(T5, O5 + B);
  U5 = min(U5, O5 + C);
  V5 = min(V5, O5 + D);
  a = min(a, d + E);
  b = min(b, d + F);
  c = min(c, d + G);
  d = min(d, d + H);
  e = min(e, d + I);
  f = min(f, d + J);
  g = min(g, d + K);
  h = min(h, d + L);
  i = min(i, d + M);
  j = min(j, d + N);
  k = min(k, n + E);
  l = min(l, n + F);
  m = min(m, n + G);
  n = min(n, n + H);
  o = min(o, n + I);
  p = min(p, n + J);
  q = min(q, n + K);
  r = min(r, n + L);
  s = min(s, n + M);
  t = min(t, n + N);
  u = min(u, x + E);
  v = min(v, x + F);
  w = min(w, x + G);
  x = min(x, x + H);
  y = min(y, x + I);
  z = min(z, x + J);
  A = min(A, x + K);
  B = min(B, x + L);
  C = min(C, x + M);
  D = min(D, x + N);
  E = min(E, H + E);
  F = min(F, H + F);
  G = min(G, H + G);
  H = min(H, H + H);
  I = min(I, H + I);
  J = min(J, H + J);
  K = min(K, H + K);
  L = min(L, H + L);
  M = min(M, H + M);
  N = min(N, H + N);
  O = min(O, R + E);
  P = min(P, R + F);
  Q = min(Q, R + G);
  R = min(R, R + H);
  S = min(S, R + I);
  T = min(T, R + J);
  U = min(U, R + K);
  V = min(V, R + L);
  W = min(W, R + M);
  X = min(X, R + N);
  Y = min(Y, b5 + E);
  Z = min(Z, b5 + F);
  a5 = min(a5, b5 + G);
  b5 = min(b5, b5 + H);
  c5 = min(c5, b5 + I);
  d5 = min(d5, b5 + J);
  e5 = min(e5, b5 + K);
  f5 = min(f5, b5 + L);
  g5 = min(g5, b5 + M);
  h5 = min(h5, b5 + N);
  i5 = min(i5, l5 + E);
  j5 = min(j5, l5 + F);
  k5 = min(k5, l5 + G);
  l5 = min(l5, l5 + H);
  m5 = min(m5, l5 + I);
  n5 = min(n5, l5 + J);
  o5 = min(o5, l5 + K);
  p5 = min(p5, l5 + L);
  q5 = min(q5, l5 + M);
  r5 = min(r5, l5 + N);
  s5 = min(s5, v5 + E);
  t5 = min(t5, v5 + F);
  u5 = min(u5, v5 + G);
  v5 = min(v5, v5 + H);
  w5 = min(w5, v5 + I);
  x5 = min(x5, v5 + J);
  y5 = min(y5, v5 + K);
  z5 = min(z5, v5 + L);
  A5 = min(A5, v5 + M);
  B5 = min(B5, v5 + N);
  C5 = min(C5, F5 + E);
  D5 = min(D5, F5 + F);
  E5 = min(E5, F5 + G);
  F5 = min(F5, F5 + H);
  G5 = min(G5, F5 + I);
  H5 = min(H5, F5 + J);
  I5 = min(I5, F5 + K);
  J5 = min(J5, F5 + L);
  K5 = min(K5, F5 + M);
  L5 = min(L5, F5 + N);
  M5 = min(M5, P5 + E);
  N5 = min(N5, P5 + F);
  O5 = min(O5, P5 + G);
  P5 = min(P5, P5 + H);
  Q5 = min(Q5, P5 + I);
  R5 = min(R5, P5 + J);
  S5 = min(S5, P5 + K);
  T5 = min(T5, P5 + L);
  U5 = min(U5, P5 + M);
  V5 = min(V5, P5 + N);
  a = min(a, e + O);
  b = min(b, e + P);
  c = min(c, e + Q);
  d = min(d, e + R);
  e = min(e, e + S);
  f = min(f, e + T);
  g = min(g, e + U);
  h = min(h, e + V);
  i = min(i, e + W);
  j = min(j, e + X);
  k = min(k, o + O);
  l = min(l, o + P);
  m = min(m, o + Q);
  n = min(n, o + R);
  o = min(o, o + S);
  p = min(p, o + T);
  q = min(q, o + U);
  r = min(r, o + V);
  s = min(s, o + W);
  t = min(t, o + X);
  u = min(u, y + O);
  v = min(v, y + P);
  w = min(w, y + Q);
  x = min(x, y + R);
  y = min(y, y + S);
  z = min(z, y + T);
  A = min(A, y + U);
  B = min(B, y + V);
  C = min(C, y + W);
  D = min(D, y + X);
  E = min(E, I + O);
  F = min(F, I + P);
  G = min(G, I + Q);
  H = min(H, I + R);
  I = min(I, I + S);
  J = min(J, I + T);
  K = min(K, I + U);
  L = min(L, I + V);
  M = min(M, I + W);
  N = min(N, I + X);
  O = min(O, S + O);
  P = min(P, S + P);
  Q = min(Q, S + Q);
  R = min(R, S + R);
  S = min(S, S + S);
  T = min(T, S + T);
  U = min(U, S + U);
  V = min(V, S + V);
  W = min(W, S + W);
  X = min(X, S + X);
  Y = min(Y, c5 + O);
  Z = min(Z, c5 + P);
  a5 = min(a5, c5 + Q);
  b5 = min(b5, c5 + R);
  c5 = min(c5, c5 + S);
  d5 = min(d5, c5 + T);
  e5 = min(e5, c5 + U);
  f5 = min(f5, c5 + V);
  g5 = min(g5, c5 + W);
  h5 = min(h5, c5 + X);
  i5 = min(i5, m5 + O);
  j5 = min(j5, m5 + P);
  k5 = min(k5, m5 + Q);
  l5 = min(l5, m5 + R);
  m5 = min(m5, m5 + S);
  n5 = min(n5, m5 + T);
  o5 = min(o5, m5 + U);
  p5 = min(p5, m5 + V);
  q5 = min(q5, m5 + W);
  r5 = min(r5, m5 + X);
  s5 = min(s5, w5 + O);
  t5 = min(t5, w5 + P);
  u5 = min(u5, w5 + Q);
  v5 = min(v5, w5 + R);
  w5 = min(w5, w5 + S);
  x5 = min(x5, w5 + T);
  y5 = min(y5, w5 + U);
  z5 = min(z5, w5 + V);
  A5 = min(A5, w5 + W);
  B5 = min(B5, w5 + X);
  C5 = min(C5, G5 + O);
  D5 = min(D5, G5 + P);
  E5 = min(E5, G5 + Q);
  F5 = min(F5, G5 + R);
  G5 = min(G5, G5 + S);
  H5 = min(H5, G5 + T);
  I5 = min(I5, G5 + U);
  J5 = min(J5, G5 + V);
  K5 = min(K5, G5 + W);
  L5 = min(L5, G5 + X);
  M5 = min(M5, Q5 + O);
  N5 = min(N5, Q5 + P);
  O5 = min(O5, Q5 + Q);
  P5 = min(P5, Q5 + R);
  Q5 = min(Q5, Q5 + S);
  R5 = min(R5, Q5 + T);
  S5 = min(S5, Q5 + U);
  T5 = min(T5, Q5 + V);
  U5 = min(U5, Q5 + W);
  V5 = min(V5, Q5 + X);
  a = min(a, f + Y);
  b = min(b, f + Z);
  c = min(c, f + a5);
  d = min(d, f + b5);
  e = min(e, f + c5);
  f = min(f, f + d5);
  g = min(g, f + e5);
  h = min(h, f + f5);
  i = min(i, f + g5);
  j = min(j, f + h5);
  k = min(k, p + Y);
  l = min(l, p + Z);
  m = min(m, p + a5);
  n = min(n, p + b5);
  o = min(o, p + c5);
  p = min(p, p + d5);
  q = min(q, p + e5);
  r = min(r, p + f5);
  s = min(s, p + g5);
  t = min(t, p + h5);
  u = min(u, z + Y);
  v = min(v, z + Z);
  w = min(w, z + a5);
  x = min(x, z + b5);
  y = min(y, z + c5);
  z = min(z, z + d5);
  A = min(A, z + e5);
  B = min(B, z + f5);
  C = min(C, z + g5);
  D = min(D, z + h5);
  E = min(E, J + Y);
  F = min(F, J + Z);
  G = min(G, J + a5);
  H = min(H, J + b5);
  I = min(I, J + c5);
  J = min(J, J + d5);
  K = min(K, J + e5);
  L = min(L, J + f5);
  M = min(M, J + g5);
  N = min(N, J + h5);
  O = min(O, T + Y);
  P = min(P, T + Z);
  Q = min(Q, T + a5);
  R = min(R, T + b5);
  S = min(S, T + c5);
  T = min(T, T + d5);
  U = min(U, T + e5);
  V = min(V, T + f5);
  W = min(W, T + g5);
  X = min(X, T + h5);
  Y = min(Y, d5 + Y);
  Z = min(Z, d5 + Z);
  a5 = min(a5, d5 + a5);
  b5 = min(b5, d5 + b5);
  c5 = min(c5, d5 + c5);
  d5 = min(d5, d5 + d5);
  e5 = min(e5, d5 + e5);
  f5 = min(f5, d5 + f5);
  g5 = min(g5, d5 + g5);
  h5 = min(h5, d5 + h5);
  i5 = min(i5, n5 + Y);
  j5 = min(j5, n5 + Z);
  k5 = min(k5, n5 + a5);
  l5 = min(l5, n5 + b5);
  m5 = min(m5, n5 + c5);
  n5 = min(n5, n5 + d5);
  o5 = min(o5, n5 + e5);
  p5 = min(p5, n5 + f5);
  q5 = min(q5, n5 + g5);
  r5 = min(r5, n5 + h5);
  s5 = min(s5, x5 + Y);
  t5 = min(t5, x5 + Z);
  u5 = min(u5, x5 + a5);
  v5 = min(v5, x5 + b5);
  w5 = min(w5, x5 + c5);
  x5 = min(x5, x5 + d5);
  y5 = min(y5, x5 + e5);
  z5 = min(z5, x5 + f5);
  A5 = min(A5, x5 + g5);
  B5 = min(B5, x5 + h5);
  C5 = min(C5, H5 + Y);
  D5 = min(D5, H5 + Z);
  E5 = min(E5, H5 + a5);
  F5 = min(F5, H5 + b5);
  G5 = min(G5, H5 + c5);
  H5 = min(H5, H5 + d5);
  I5 = min(I5, H5 + e5);
  J5 = min(J5, H5 + f5);
  K5 = min(K5, H5 + g5);
  L5 = min(L5, H5 + h5);
  M5 = min(M5, R5 + Y);
  N5 = min(N5, R5 + Z);
  O5 = min(O5, R5 + a5);
  P5 = min(P5, R5 + b5);
  Q5 = min(Q5, R5 + c5);
  R5 = min(R5, R5 + d5);
  S5 = min(S5, R5 + e5);
  T5 = min(T5, R5 + f5);
  U5 = min(U5, R5 + g5);
  V5 = min(V5, R5 + h5);
  a = min(a, g + i5);
  b = min(b, g + j5);
  c = min(c, g + k5);
  d = min(d, g + l5);
  e = min(e, g + m5);
  f = min(f, g + n5);
  g = min(g, g + o5);
  h = min(h, g + p5);
  i = min(i, g + q5);
  j = min(j, g + r5);
  k = min(k, q + i5);
  l = min(l, q + j5);
  m = min(m, q + k5);
  n = min(n, q + l5);
  o = min(o, q + m5);
  p = min(p, q + n5);
  q = min(q, q + o5);
  r = min(r, q + p5);
  s = min(s, q + q5);
  t = min(t, q + r5);
  u = min(u, A + i5);
  v = min(v, A + j5);
  w = min(w, A + k5);
  x = min(x, A + l5);
  y = min(y, A + m5);
  z = min(z, A + n5);
  A = min(A, A + o5);
  B = min(B, A + p5);
  C = min(C, A + q5);
  D = min(D, A + r5);
  E = min(E, K + i5);
  F = min(F, K + j5);
  G = min(G, K + k5);
  H = min(H, K + l5);
  I = min(I, K + m5);
  J = min(J, K + n5);
  K = min(K, K + o5);
  L = min(L, K + p5);
  M = min(M, K + q5);
  N = min(N, K + r5);
  O = min(O, U + i5);
  P = min(P, U + j5);
  Q = min(Q, U + k5);
  R = min(R, U + l5);
  S = min(S, U + m5);
  T = min(T, U + n5);
  U = min(U, U + o5);
  V = min(V, U + p5);
  W = min(W, U + q5);
  X = min(X, U + r5);
  Y = min(Y, e5 + i5);
  Z = min(Z, e5 + j5);
  a5 = min(a5, e5 + k5);
  b5 = min(b5, e5 + l5);
  c5 = min(c5, e5 + m5);
  d5 = min(d5, e5 + n5);
  e5 = min(e5, e5 + o5);
  f5 = min(f5, e5 + p5);
  g5 = min(g5, e5 + q5);
  h5 = min(h5, e5 + r5);
  i5 = min(i5, o5 + i5);
  j5 = min(j5, o5 + j5);
  k5 = min(k5, o5 + k5);
  l5 = min(l5, o5 + l5);
  m5 = min(m5, o5 + m5);
  n5 = min(n5, o5 + n5);
  o5 = min(o5, o5 + o5);
  p5 = min(p5, o5 + p5);
  q5 = min(q5, o5 + q5);
  r5 = min(r5, o5 + r5);
  s5 = min(s5, y5 + i5);
  t5 = min(t5, y5 + j5);
  u5 = min(u5, y5 + k5);
  v5 = min(v5, y5 + l5);
  w5 = min(w5, y5 + m5);
  x5 = min(x5, y5 + n5);
  y5 = min(y5, y5 + o5);
  z5 = min(z5, y5 + p5);
  A5 = min(A5, y5 + q5);
  B5 = min(B5, y5 + r5);
  C5 = min(C5, I5 + i5);
  D5 = min(D5, I5 + j5);
  E5 = min(E5, I5 + k5);
  F5 = min(F5, I5 + l5);
  G5 = min(G5, I5 + m5);
  H5 = min(H5, I5 + n5);
  I5 = min(I5, I5 + o5);
  J5 = min(J5, I5 + p5);
  K5 = min(K5, I5 + q5);
  L5 = min(L5, I5 + r5);
  M5 = min(M5, S5 + i5);
  N5 = min(N5, S5 + j5);
  O5 = min(O5, S5 + k5);
  P5 = min(P5, S5 + l5);
  Q5 = min(Q5, S5 + m5);
  R5 = min(R5, S5 + n5);
  S5 = min(S5, S5 + o5);
  T5 = min(T5, S5 + p5);
  U5 = min(U5, S5 + q5);
  V5 = min(V5, S5 + r5);
  a = min(a, h + s5);
  b = min(b, h + t5);
  c = min(c, h + u5);
  d = min(d, h + v5);
  e = min(e, h + w5);
  f = min(f, h + x5);
  g = min(g, h + y5);
  h = min(h, h + z5);
  i = min(i, h + A5);
  j = min(j, h + B5);
  k = min(k, r + s5);
  l = min(l, r + t5);
  m = min(m, r + u5);
  n = min(n, r + v5);
  o = min(o, r + w5);
  p = min(p, r + x5);
  q = min(q, r + y5);
  r = min(r, r + z5);
  s = min(s, r + A5);
  t = min(t, r + B5);
  u = min(u, B + s5);
  v = min(v, B + t5);
  w = min(w, B + u5);
  x = min(x, B + v5);
  y = min(y, B + w5);
  z = min(z, B + x5);
  A = min(A, B + y5);
  B = min(B, B + z5);
  C = min(C, B + A5);
  D = min(D, B + B5);
  E = min(E, L + s5);
  F = min(F, L + t5);
  G = min(G, L + u5);
  H = min(H, L + v5);
  I = min(I, L + w5);
  J = min(J, L + x5);
  K = min(K, L + y5);
  L = min(L, L + z5);
  M = min(M, L + A5);
  N = min(N, L + B5);
  O = min(O, V + s5);
  P = min(P, V + t5);
  Q = min(Q, V + u5);
  R = min(R, V + v5);
  S = min(S, V + w5);
  T = min(T, V + x5);
  U = min(U, V + y5);
  V = min(V, V + z5);
  W = min(W, V + A5);
  X = min(X, V + B5);
  Y = min(Y, f5 + s5);
  Z = min(Z, f5 + t5);
  a5 = min(a5, f5 + u5);
  b5 = min(b5, f5 + v5);
  c5 = min(c5, f5 + w5);
  d5 = min(d5, f5 + x5);
  e5 = min(e5, f5 + y5);
  f5 = min(f5, f5 + z5);
  g5 = min(g5, f5 + A5);
  h5 = min(h5, f5 + B5);
  i5 = min(i5, p5 + s5);
  j5 = min(j5, p5 + t5);
  k5 = min(k5, p5 + u5);
  l5 = min(l5, p5 + v5);
  m5 = min(m5, p5 + w5);
  n5 = min(n5, p5 + x5);
  o5 = min(o5, p5 + y5);
  p5 = min(p5, p5 + z5);
  q5 = min(q5, p5 + A5);
  r5 = min(r5, p5 + B5);
  s5 = min(s5, z5 + s5);
  t5 = min(t5, z5 + t5);
  u5 = min(u5, z5 + u5);
  v5 = min(v5, z5 + v5);
  w5 = min(w5, z5 + w5);
  x5 = min(x5, z5 + x5);
  y5 = min(y5, z5 + y5);
  z5 = min(z5, z5 + z5);
  A5 = min(A5, z5 + A5);
  B5 = min(B5, z5 + B5);
  C5 = min(C5, J5 + s5);
  D5 = min(D5, J5 + t5);
  E5 = min(E5, J5 + u5);
  F5 = min(F5, J5 + v5);
  G5 = min(G5, J5 + w5);
  H5 = min(H5, J5 + x5);
  I5 = min(I5, J5 + y5);
  J5 = min(J5, J5 + z5);
  K5 = min(K5, J5 + A5);
  L5 = min(L5, J5 + B5);
  M5 = min(M5, T5 + s5);
  N5 = min(N5, T5 + t5);
  O5 = min(O5, T5 + u5);
  P5 = min(P5, T5 + v5);
  Q5 = min(Q5, T5 + w5);
  R5 = min(R5, T5 + x5);
  S5 = min(S5, T5 + y5);
  T5 = min(T5, T5 + z5);
  U5 = min(U5, T5 + A5);
  V5 = min(V5, T5 + B5);
  a = min(a, i + C5);
  b = min(b, i + D5);
  c = min(c, i + E5);
  d = min(d, i + F5);
  e = min(e, i + G5);
  f = min(f, i + H5);
  g = min(g, i + I5);
  h = min(h, i + J5);
  i = min(i, i + K5);
  j = min(j, i + L5);
  k = min(k, s + C5);
  l = min(l, s + D5);
  m = min(m, s + E5);
  n = min(n, s + F5);
  o = min(o, s + G5);
  p = min(p, s + H5);
  q = min(q, s + I5);
  r = min(r, s + J5);
  s = min(s, s + K5);
  t = min(t, s + L5);
  u = min(u, C + C5);
  v = min(v, C + D5);
  w = min(w, C + E5);
  x = min(x, C + F5);
  y = min(y, C + G5);
  z = min(z, C + H5);
  A = min(A, C + I5);
  B = min(B, C + J5);
  C = min(C, C + K5);
  D = min(D, C + L5);
  E = min(E, M + C5);
  F = min(F, M + D5);
  G = min(G, M + E5);
  H = min(H, M + F5);
  I = min(I, M + G5);
  J = min(J, M + H5);
  K = min(K, M + I5);
  L = min(L, M + J5);
  M = min(M, M + K5);
  N = min(N, M + L5);
  O = min(O, W + C5);
  P = min(P, W + D5);
  Q = min(Q, W + E5);
  R = min(R, W + F5);
  S = min(S, W + G5);
  T = min(T, W + H5);
  U = min(U, W + I5);
  V = min(V, W + J5);
  W = min(W, W + K5);
  X = min(X, W + L5);
  Y = min(Y, g5 + C5);
  Z = min(Z, g5 + D5);
  a5 = min(a5, g5 + E5);
  b5 = min(b5, g5 + F5);
  c5 = min(c5, g5 + G5);
  d5 = min(d5, g5 + H5);
  e5 = min(e5, g5 + I5);
  f5 = min(f5, g5 + J5);
  g5 = min(g5, g5 + K5);
  h5 = min(h5, g5 + L5);
  i5 = min(i5, q5 + C5);
  j5 = min(j5, q5 + D5);
  k5 = min(k5, q5 + E5);
  l5 = min(l5, q5 + F5);
  m5 = min(m5, q5 + G5);
  n5 = min(n5, q5 + H5);
  o5 = min(o5, q5 + I5);
  p5 = min(p5, q5 + J5);
  q5 = min(q5, q5 + K5);
  r5 = min(r5, q5 + L5);
  s5 = min(s5, A5 + C5);
  t5 = min(t5, A5 + D5);
  u5 = min(u5, A5 + E5);
  v5 = min(v5, A5 + F5);
  w5 = min(w5, A5 + G5);
  x5 = min(x5, A5 + H5);
  y5 = min(y5, A5 + I5);
  z5 = min(z5, A5 + J5);
  A5 = min(A5, A5 + K5);
  B5 = min(B5, A5 + L5);
  C5 = min(C5, K5 + C5);
  D5 = min(D5, K5 + D5);
  E5 = min(E5, K5 + E5);
  F5 = min(F5, K5 + F5);
  G5 = min(G5, K5 + G5);
  H5 = min(H5, K5 + H5);
  I5 = min(I5, K5 + I5);
  J5 = min(J5, K5 + J5);
  K5 = min(K5, K5 + K5);
  L5 = min(L5, K5 + L5);
  M5 = min(M5, U5 + C5);
  N5 = min(N5, U5 + D5);
  O5 = min(O5, U5 + E5);
  P5 = min(P5, U5 + F5);
  Q5 = min(Q5, U5 + G5);
  R5 = min(R5, U5 + H5);
  S5 = min(S5, U5 + I5);
  T5 = min(T5, U5 + J5);
  U5 = min(U5, U5 + K5);
  V5 = min(V5, U5 + L5);
  a = min(a, j + M5);
  b = min(b, j + N5);
  c = min(c, j + O5);
  d = min(d, j + P5);
  e = min(e, j + Q5);
  f = min(f, j + R5);
  g = min(g, j + S5);
  h = min(h, j + T5);
  i = min(i, j + U5);
  j = min(j, j + V5);
  k = min(k, t + M5);
  l = min(l, t + N5);
  m = min(m, t + O5);
  n = min(n, t + P5);
  o = min(o, t + Q5);
  p = min(p, t + R5);
  q = min(q, t + S5);
  r = min(r, t + T5);
  s = min(s, t + U5);
  t = min(t, t + V5);
  u = min(u, D + M5);
  v = min(v, D + N5);
  w = min(w, D + O5);
  x = min(x, D + P5);
  y = min(y, D + Q5);
  z = min(z, D + R5);
  A = min(A, D + S5);
  B = min(B, D + T5);
  C = min(C, D + U5);
  D = min(D, D + V5);
  E = min(E, N + M5);
  F = min(F, N + N5);
  G = min(G, N + O5);
  H = min(H, N + P5);
  I = min(I, N + Q5);
  J = min(J, N + R5);
  K = min(K, N + S5);
  L = min(L, N + T5);
  M = min(M, N + U5);
  N = min(N, N + V5);
  O = min(O, X + M5);
  P = min(P, X + N5);
  Q = min(Q, X + O5);
  R = min(R, X + P5);
  S = min(S, X + Q5);
  T = min(T, X + R5);
  U = min(U, X + S5);
  V = min(V, X + T5);
  W = min(W, X + U5);
  X = min(X, X + V5);
  Y = min(Y, h5 + M5);
  Z = min(Z, h5 + N5);
  a5 = min(a5, h5 + O5);
  b5 = min(b5, h5 + P5);
  c5 = min(c5, h5 + Q5);
  d5 = min(d5, h5 + R5);
  e5 = min(e5, h5 + S5);
  f5 = min(f5, h5 + T5);
  g5 = min(g5, h5 + U5);
  h5 = min(h5, h5 + V5);
  i5 = min(i5, r5 + M5);
  j5 = min(j5, r5 + N5);
  k5 = min(k5, r5 + O5);
  l5 = min(l5, r5 + P5);
  m5 = min(m5, r5 + Q5);
  n5 = min(n5, r5 + R5);
  o5 = min(o5, r5 + S5);
  p5 = min(p5, r5 + T5);
  q5 = min(q5, r5 + U5);
  r5 = min(r5, r5 + V5);
  s5 = min(s5, B5 + M5);
  t5 = min(t5, B5 + N5);
  u5 = min(u5, B5 + O5);
  v5 = min(v5, B5 + P5);
  w5 = min(w5, B5 + Q5);
  x5 = min(x5, B5 + R5);
  y5 = min(y5, B5 + S5);
  z5 = min(z5, B5 + T5);
  A5 = min(A5, B5 + U5);
  B5 = min(B5, B5 + V5);
  C5 = min(C5, L5 + M5);
  D5 = min(D5, L5 + N5);
  E5 = min(E5, L5 + O5);
  F5 = min(F5, L5 + P5);
  G5 = min(G5, L5 + Q5);
  H5 = min(H5, L5 + R5);
  I5 = min(I5, L5 + S5);
  J5 = min(J5, L5 + T5);
  K5 = min(K5, L5 + U5);
  L5 = min(L5, L5 + V5);
  M5 = min(M5, V5 + M5);
  N5 = min(N5, V5 + N5);
  O5 = min(O5, V5 + O5);
  P5 = min(P5, V5 + P5);
  Q5 = min(Q5, V5 + Q5);
  R5 = min(R5, V5 + R5);
  S5 = min(S5, V5 + S5);
  T5 = min(T5, V5 + T5);
  U5 = min(U5, V5 + U5);
  V5 = min(V5, V5 + V5);
  int _a = 0;
  _a = max(_a, a);
  _a = max(_a, b);
  _a = max(_a, c);
  _a = max(_a, d);
  _a = max(_a, e);
  _a = max(_a, f);
  _a = max(_a, g);
  _a = max(_a, h);
  _a = max(_a, i);
  _a = max(_a, j);
  _a = max(_a, k);
  _a = max(_a, l);
  _a = max(_a, m);
  _a = max(_a, n);
  _a = max(_a, o);
  _a = max(_a, p);
  _a = max(_a, q);
  _a = max(_a, r);
  _a = max(_a, s);
  _a = max(_a, t);
  _a = max(_a, u);
  _a = max(_a, v);
  _a = max(_a, w);
  _a = max(_a, x);
  _a = max(_a, y);
  _a = max(_a, z);
  _a = max(_a, A);
  _a = max(_a, B);
  _a = max(_a, C);
  _a = max(_a, D);
  _a = max(_a, E);
  _a = max(_a, F);
  _a = max(_a, G);
  _a = max(_a, H);
  _a = max(_a, I);
  _a = max(_a, J);
  _a = max(_a, K);
  _a = max(_a, L);
  _a = max(_a, M);
  _a = max(_a, N);
  _a = max(_a, O);
  _a = max(_a, P);
  _a = max(_a, Q);
  _a = max(_a, R);
  _a = max(_a, S);
  _a = max(_a, T);
  _a = max(_a, U);
  _a = max(_a, V);
  _a = max(_a, W);
  _a = max(_a, X);
  _a = max(_a, Y);
  _a = max(_a, Z);
  _a = max(_a, a5);
  _a = max(_a, b5);
  _a = max(_a, c5);
  _a = max(_a, d5);
  _a = max(_a, e5);
  _a = max(_a, f5);
  _a = max(_a, g5);
  _a = max(_a, h5);
  _a = max(_a, i5);
  _a = max(_a, j5);
  _a = max(_a, k5);
  _a = max(_a, l5);
  _a = max(_a, m5);
  _a = max(_a, n5);
  _a = max(_a, o5);
  _a = max(_a, p5);
  _a = max(_a, q5);
  _a = max(_a, r5);
  _a = max(_a, s5);
  _a = max(_a, t5);
  _a = max(_a, u5);
  _a = max(_a, v5);
  _a = max(_a, w5);
  _a = max(_a, x5);
  _a = max(_a, y5);
  _a = max(_a, z5);
  _a = max(_a, A5);
  _a = max(_a, B5);
  _a = max(_a, C5);
  _a = max(_a, D5);
  _a = max(_a, E5);
  _a = max(_a, F5);
  _a = max(_a, G5);
  _a = max(_a, H5);
  _a = max(_a, I5);
  _a = max(_a, J5);
  _a = max(_a, K5);
  _a = max(_a, L5);
  _a = max(_a, M5);
  _a = max(_a, N5);
  _a = max(_a, O5);
  _a = max(_a, P5);
  _a = max(_a, Q5);
  _a = max(_a, R5);
  _a = max(_a, S5);
  _a = max(_a, T5);
  _a = max(_a, U5);
  _a = max(_a, V5);
  printf("%d\n", _a);
}
int main() {
  scanf("%d", &_n);
  cin >> a;
  cin >> b;
  cin >> c;
  cin >> d;
  cin >> e;
  cin >> f;
  cin >> g;
  cin >> h;
  cin >> i;
  cin >> j;
  cin >> k;
  cin >> l;
  cin >> m;
  cin >> n;
  cin >> o;
  cin >> p;
  cin >> q;
  cin >> r;
  cin >> s;
  cin >> t;
  cin >> u;
  cin >> v;
  cin >> w;
  cin >> x;
  cin >> y;
  cin >> z;
  cin >> A;
  cin >> B;
  cin >> C;
  cin >> D;
  cin >> E;
  cin >> F;
  cin >> G;
  cin >> H;
  cin >> I;
  cin >> J;
  cin >> K;
  cin >> L;
  cin >> M;
  cin >> N;
  cin >> O;
  cin >> P;
  cin >> Q;
  cin >> R;
  cin >> S;
  cin >> T;
  cin >> U;
  cin >> V;
  cin >> W;
  cin >> X;
  cin >> Y;
  cin >> Z;
  cin >> a5;
  cin >> b5;
  cin >> c5;
  cin >> d5;
  cin >> e5;
  cin >> f5;
  cin >> g5;
  cin >> h5;
  cin >> i5;
  cin >> j5;
  cin >> k5;
  cin >> l5;
  cin >> m5;
  cin >> n5;
  cin >> o5;
  cin >> p5;
  cin >> q5;
  cin >> r5;
  cin >> s5;
  cin >> t5;
  cin >> u5;
  cin >> v5;
  cin >> w5;
  cin >> x5;
  cin >> y5;
  cin >> z5;
  cin >> A5;
  cin >> B5;
  cin >> C5;
  cin >> D5;
  cin >> E5;
  cin >> F5;
  cin >> G5;
  cin >> H5;
  cin >> I5;
  cin >> J5;
  cin >> K5;
  cin >> L5;
  cin >> M5;
  cin >> N5;
  cin >> O5;
  cin >> P5;
  cin >> Q5;
  cin >> R5;
  cin >> S5;
  cin >> T5;
  cin >> U5;
  cin >> V5;
  _n == 1
      ? solve1()
      : (_n == 2
             ? solve2()
             : (_n == 3
                    ? solve3()
                    : (_n == 4
                           ? solve4()
                           : (_n == 5
                                  ? solve5()
                                  : (_n == 6
                                         ? solve6()
                                         : (_n == 7
                                                ? solve7()
                                                : (_n == 8
                                                       ? solve8()
                                                       : (_n == 9
                                                              ? solve9()
                                                              : (solve10())))))))));
  return 0;
}
