# -*- coding: utf-8 -*- """ 6 0 2 4 -1 -1 -1 2 0 9 7 -1 -1 4 9 0 8 1 -1 -1 7 8 0 3 1 -1 -1 1 3 0 2 -1 -1 -1 1 2 0 6 0 2 1 -1 -1 -1 2 0 9 7 -1 -1 1 9 0 8 4 -1 -1 7 8 0 3 1 -1 -1 4 3 0 5 -1 -1 -1 1 5 0 """ 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: 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 ( "%4d" %(W[i][j]), end="" ) print(); 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();