INF float inf int input for in range row list map int input split appe

INF = float("inf")



N = int(input())

W = []  

for i in range(N):

  row = list(map(int, input().split()))

  W.append(row)



for i in range(N):

  for j in range(N):

    if W[i][j] == 0 and i != j: W[i][j] = INF

'''  

print ( "Весовая матрица графа: " )

for i in range(N):

  for j in range(N):

    if W[i][j] == INF: print ( "   *", end="" )

    else: print ( "%4d" %W[i][j], end="" )

  print();    

'''



P = []

for i in range(N):

  P.append([i]*N)

  P[i][i] = -1



for k in range(N):

  for i in range(N):

    for j in range(N):

      if W[i][k] + W[k][j] < W[i][j]:

        W[i][j] = W[i][k] + W[k][j]

        P[i][j] = P[k][j]



 

#print ("\nМатрица кратчайших расстояний:");

for i in range(N):

  for j in range(N): print ( (W[i][j]), end=" " )

  print()

  

'''

print(W[A-1][B-1])

'''

'''

print ( "\nВспомогательная матрица:");

for i in range(N):

  for j in range(N):

    print( "%4d" %P[i][j], end="" )

  print()

print()

'''



'''

for i in range(N):

  print ("Кратчайшие маршруты из вершины:", i+1)

  for k in range(N):

    if k != i:

      j = k

      while j != -1:

        print ( "%2d" %(j+1), end="" )

        if j != i:

          print ( " <= ", end="" );

        j = P[i][j];

      print()

'''

'''

#print ("Кратчайшие маршруты из вершины:", B)

if W[A-1][B-1] != 0:

    for k in range(A):

        if k != i:

          j = k 

          while j != -1:

            if k == A-1:

                print ((j+1), end=" " )

            j = P[B-1][j]

'''