from heapq import heappop, heappush

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))
    
    
    L = [[] for _ in range(N+1)]

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


    return N , L


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

    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 


d = dijkstra(1,*citire())

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