import heapq
import math


def read_graph(filename):
    graph = {}

    with open(filename) as file:
        values = file.readline().split()

        graph['n'] = int(values[0])
        graph['m'] = int(values[1])
        graph['edges'] = {}

        for i in range(0, graph['n']):
            graph['edges'][i] = []

        for i in range(0, graph['m']):
            values = file.readline().split()
            a = int(values[0]) - 1
            b = int(values[1]) - 1
            c = int(values[2])
            graph['edges'][a].append((b, c))

    return graph


def dijkstra(graph, source):
    hp = []
    dist = []

    for i in range(0, graph['n']):
        dist.append(math.inf)
        heapq.heappush(hp, (dist[i], i))

    dist[source] = 0

    while len(hp) > 0:
        vert = heapq.heappop(hp)
        for edge in graph['edges'][vert[1]]:
            alt = dist[vert[1]] + edge[1]
            if alt < dist[edge[0]]:
                dist[edge[0]] = alt

                for i in range(0, len(hp)):
                    if hp[i][1] == edge[0]:
                        hp[i] = (alt, edge[0])
                        heapq.heapify(hp)
                        break

    return dist


graph = read_graph('dijkstra.in')
dist = dijkstra(graph, 0)

with open('dijkstra.out', 'w') as file:
    for i in range(1, len(dist)):
        if dist[i] == math.inf:
            file.write('0 ')
        else:
            file.write(str(dist[i]) + ' ')