import math
import queue

def read_gen(fname):
    with open(fname, 'rt') as fin:
        for line in fin:
            for val in line.split():
                yield int(val)

def solve(n, m, g, start):
    dist = [math.inf for _ in range(n + 1)]
    dist[start] = 0
    pq = queue.PriorityQueue(maxsize=m)
    pq.put((dist[start], start))

    while pq.empty() is False:
        d, node = pq.get()
        if d > dist[node]: continue

        for nn, c in g[node]:
            new_d = dist[node] + c
            if new_d < dist[nn]:
                dist[nn] = new_d
                pq.put((dist[nn], nn))
    return dist

if __name__ == "__main__":
    it = read_gen('dijkstra.in')
    n, m = next(it), next(it)
    g = {x: [] for x in range(1, n + 1)}
    for _ in range(m):
        x, y, c = next(it), next(it), next(it)
        g[x].append((y, c))
    dist = solve(n, m, g, 1)

    with open('dijkstra.out', 'wt') as fout:
        for i in range(2, n + 1):
            if dist[i] == math.inf:
                v = 0
            else:
                v = dist[i]
            fout.write('{} '.format(v))
        fout.write('\n')