N,M = map(int,input().split())
inf = 10 ** 18
dist = [[inf] * N for _ in range(N)]
for _ in range(M):
    s,t,d = map(int,input().split())
    dist[s-1][t-1] = min(dist[s-1][t-1],d)
for i in range(N):
    dist[i][i] = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if dist[i][k] == inf or dist[k][j] == inf:continue
            dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
for i in range(N):
    for j in range(N):
        if dist[i][j] == inf:
            dist[i][j] = 0
for i in range(N):
    print(sum(dist[i]))