import sys
input = sys.stdin.readline
INF = 10**9
N,M = int(input()),int(input())
graph = [[INF]*(N+1) for i in range(N+1)]
path = [[[i] for i in range(N+1)] for i in range(N+1)]
for i in range(M):
x,y,w = map(int,input().split())
graph[x][y] = min(graph[x][y],w)
for k in range(1,N+1):
for i in range(1,N+1):
for j in range(1,N+1):
if i == j:
continue
if graph[i][j] > graph[i][k]+graph[k][j]:
graph[i][j] = graph[i][k]+graph[k][j]
path[i][j] = path[i][k]+path[k][j]
for i in range(1,N+1):
for j in range(1,N+1):
if graph[i][j] == INF:
print(0,end=" ")
else:
print(graph[i][j],end=" ")
print()
for i in range(1,N+1):
for j in range(1,N+1):
if graph[i][j] == INF:
print(0)
else:
print(len(path[i][j])+1,i,*path[i][j])
플로이드 워셜 알고리즘 기본문제에 경로추적을 더한 문제
path 배열을 만들어서 각 배열에 경로를 넣은 후, 경로가 갱신될때마다 그래프값을 더해주면서 경로도 같이 더해주면 된다.