#!/usr/bin/env python3

import sys

sys.stdout = open('dijkstra.out', 'w')

with open('dijkstra.in', 'r') as f:
    readInts = lambda: map(int, f.readline().split())

    N, M = tuple(readInts())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        A, B, C = tuple(readInts())
        edges[A - 1].append((B - 1, C))

    D, P, h, H = [sys.maxsize] * N, list(range(N)), list(range(N)), N
    D[0] = 0

    def hpop():
        global H
        H -= 1
        h[0], h[H] = h[H], h[0]
        P[h[0]] = 0

        idx = 0
        while True:
            minIdx = idx
            if idx * 2 + 1 < H and D[h[idx]] > D[h[idx * 2 + 1]]:
                minIdx = idx * 2 + 1
            if idx * 2 + 2 < H and D[h[minIdx]] > D[h[idx * 2 + 2]]:
                minIdx = idx * 2 + 2
            if minIdx != idx:
                h[idx], h[minIdx] = h[minIdx], h[idx]
                P[h[idx]], P[h[minIdx]] = idx, minIdx
                idx = minIdx
            else:
                break
        
        return h.pop()

    def hup(idx):
        while idx > 0:
            pIdx = (idx - 1) // 2
            if D[h[idx]] < D[h[pIdx]]:
                h[idx], h[pIdx] = h[pIdx], h[idx]
                P[h[idx]], P[h[pIdx]] = idx, pIdx
                idx = pIdx
            else:
                break

    for _ in range(N):
        node = hpop()
        for B, C in edges[node]:
            if D[node] + C < D[B]:
                D[B] = D[node] + C
                hup(P[B])

    print(' '.join(str(x if x != sys.maxsize else 0) for i, x in enumerate(D) if i > 0))