import heapq
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    s,t,d=map(int,input().split())
    g[s-1].append((t-1,d))
def dijkstra(s):
    dst=[0]*n
    confirmed=[False]*n
    q=[]
    heapq.heappush(q,(0,s))
    while q:
        now_dst,now_place=heapq.heappop(q)
        if confirmed[now_place]:
            continue
        dst[now_place]=now_dst
        confirmed[now_place]=True
        for to_place,cost in g[now_place]:
            if not confirmed[to_place]:
                to_dst=now_dst+cost
                heapq.heappush(q,(to_dst,to_place))
    return sum(dst)
for i in range(n):
    print(dijkstra(i))