'''
# Sample code to perform I/O:

name = input()                  # Reading input from STDIN
print('Hi, %s.' % name)         # Writing output to STDOUT

# Warning: Printing unwanted or ill-formatted data to output will cause the test cases to fail
'''

# Write your code here
import heapq
from collections import defaultdict

f = open("dijkstra.in","r")

line = f.readline().split(" ")
v = int(line[0])
e = int(line[1])

graph = [ [] for _ in range(v)]
for _ in range(e):
    line = f.readline().split(" ")
    graph[int(line[0])-1].append( [int(line[1])-1,int(line[2])] )

f.close()

hq = []
heapq.heappush(hq, (0, 0))
visited = set()
sol = defaultdict(lambda: 10**9)

while hq:
    val, node = heapq.heappop(hq)
    if node not in visited:
        sol[node] = val

    for entry in graph[node]:
        n, d = entry
        if n in visited:
            continue
        else:
            heapq.heappush(hq, (d+val, n))

    visited.add(node)

with open("dijkstra.out","w") as f:
    for n in range(1, v):
        f.write(str(sol[n]))
        f.write(" ")