fi = open("dijkstra.in", "r")
fo = open("dijkstra.out", "w")

INF = 1000000005

def citeste():
    ret = fi.readline().split()
    ret = map(int, ret)
    return ret

G = [[] for i in range(50005)]

dist = [None] * 50005

def getDijkstra(n, m):
    for i in range(1, n + 1):
        dist[i] = INF
    
    Q = set()

    dist[1] = 0
    Q.add((0, 1))

    while Q:
        #print("da")
        nod = min(Q)[1]
        distScot = min(Q)[0]
        #print(str(nod) + " " + str(distScot))
        Q.remove(min(Q))
        if distScot != dist[nod]:
            continue
        for v in G[nod]:
            vNod = v[0]
            distV = v[1]
            if distScot + distV < dist[vNod]:
                dist[vNod] = distScot + distV
                Q.add((dist[vNod], vNod))
        

n, m = citeste()

for i in range(0, m):
    u, v, c = citeste()
    G[u].append((v, c))
    #G[v].append((u, c))

getDijkstra(n, m)

for i in range(2, n + 1):
    if dist[i] != INF:
        fo.write(str(dist[i]) + " ")
    else:
        fo.write("0 ")