from heapq import heapify, heappop, heappush
import heapq as hp


def citire():
    with open('dijkstra.in') as file:
        lista_muchii_costuri = []
        N , M = map(int,file.readline().split())
        for line in file:
            m1, m2 , cost = map(int,line.split())
            lista_muchii_costuri.append((m1,m2,cost))

    return N , lista_muchii_costuri




def dijkstra(s = 0, n = 5, muchii= []):


    L = [[] for _ in range(n+1)]

    for u , v , cost in muchii:
        L[u].append((v,cost))


    d = [float('inf')] * (n+1)
    d[s] = 0
    vis = [0]*(n+1)

    Pq = []
    heappush(Pq,(d[s],s))
    
    
    while len(Pq) > 0:
        curr_dist, node = heappop(Pq)

        if vis[node] == 1:
            continue
        
        vis[node] = 1
        for x in L[node]:
            vecin = x[0]
            cost = x[1]
            if d[vecin] > d[node]+cost:
                d[vecin] = d[node] + cost
            heappush(Pq,(d[vecin],vecin))
    return d 

N , lista_muchii_costuri = citire()

d = dijkstra(1,N,lista_muchii_costuri)

with open('dijkstra.out', 'w') as file:
    print(*d[2:], file = file)