import sys
input=sys.stdin.readline

N, M=map(int,input().split())
abc=[list(map(int,input().split())) for _ in range(M)]

dist=[[float('inf')]*N for _ in range(N)]

for i in range(N):
  dist[i][i]=0

for i in range(M):
  a=abc[i][0]-1
  b=abc[i][1]-1
  c=abc[i][2]-1
  dist[a][b]=c
  dist[b][a]=c

for i in range(N):
  for j in range(N):
    for k in range(N):
      dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
      dist[k][j]=dist[j][k]