INF = 1 << 60

n, m = map(int, input().split())
dist = [[INF for _ in range(n)] for _ in range(n)]
for v in range(n):
  dist[v][v] = 0

for _ in range(m):
  s, t, d = map(int, input().split())
  s -= 1
  t -= 1
  dist[s][t] = min(dist[s][t], d)

for k in range(n):
  dk = dist[k]
  for u in range(n):
    du = dist[u]
    for v in range(n):
      if du[k] < INF and dk[v] < INF and du[v] > du[k] + dk[v]:
        du[v] = du[k] + dk[v]

for i in range(n):
  print(sum(dist[i]))