from heapq import heappop, heappush
file1 = open('dijkstra.in', 'r')
Lines = file1.readlines()


inf = 99999999
n, m = Lines[0].split()
n = int(n)
m = int(m)

graph = {}
frontier = []
frontier_cost = {}

for i in range(n+1):
    frontier_cost[i] = inf

for line in Lines[1:]:
    x, y, c = line.split()
    x = int(x)
    y = int(y)
    c = int(c)

    if x not in graph:
        graph[x] = []
    graph[x].append((y, c))

visited = 1
frontier.append((0, 1))
frontier_cost[1] = 0

while visited != n and frontier:
    cost_node, node = heappop(frontier)
    if node not in graph:
        continue
    for neigh, cost in graph[node]:
        if cost_node + cost < frontier_cost[neigh]:
            if frontier_cost[neigh] == inf:
                visited += 1
            frontier_cost[neigh] = cost_node + cost
            heappush(frontier, (cost_node + cost, neigh))


file_out = open('dijkstra.out', 'w')
for i in range(2, n + 1):
    if i not in frontier_cost:
        continue
    if frontier_cost[i] != inf:

        file_out.write(str(frontier_cost[i]) + " ")
    else:
        file_out.write("0 ")