n = int(input())
matr = [list(map(int, input().split())) for i in range(n)]
for k in range(n): #алгоритм Флойда
for i in range(n):
for j in range(n):
if matr[i][j] > matr[i][k] + matr[k][j]:
matr[i][j] = matr[i][k] + matr[k][j]
print(max([max(string) for string in matr]))