import heapq

def solve():
    # Citim toate datele dintr-un singur apel pentru a optimiza I/O-ul în Python
    try:
        with open('dijkstra.in', 'r') as fin:
            data = fin.read().split()
    except FileNotFoundError:
        return

    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    # Construim lista de adiacenta
    graph = [[] for _ in range(N + 1)]
    idx = 2
    for _ in range(M):
        u = int(data[idx])
        v = int(data[idx+1])
        w = int(data[idx+2])
        graph[u].append((v, w))
        idx += 3

    # Initializam distantele cu infinit, iar distanta de la nodul de start (1) cu 0
    INF = float('inf')
    dist = [INF] * (N + 1)
    dist[1] = 0

    # Priority queue: stocheaza tupluri de forma (distanta_acumulata, nod)
    pq = [(0, 1)]

    while pq:
        d, u = heapq.heappop(pq)

        # Daca am extras o distanta mai mare decat cea minima gasita deja, ignoram
        if d > dist[u]:
            continue

        # Relaxarea arcelor
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    # Construim raspunsul
    rezultat = []
    for i in range(2, N + 1):
        # Conform cerintei, daca nu exista drum se afiseaza 0
        if dist[i] == INF:
            rezultat.append("0")
        else:
            rezultat.append(str(dist[i]))

    # Scriem datele de iesire
    with open('dijkstra.out', 'w') as fout:
        fout.write(" ".join(rezultat) + "\n")

if __name__ == '__main__':
    solve()