import heapq

edges = []
with open("dijkstra.in") as file:
    n, m = [int(x) for x in next(file).split()]
    
    for i in range(n+1):
        edges.append([])
    
    edges = tuple(edges)
    
    for i in range(m):
        line = file.readline()
        nums = line.split()
        
        edges[int(nums[0])].append((nums[1],int(nums[2])))      
        del nums
        del line

del file


def calculate_distances():
    dist = [1000000000 for i in range(n+1)]
    dist[int(startVertex)] = 0
    
    priorityQ = [(0, startVertex)]
    while len(priorityQ):
        currentDistance, currentVertex = heapq.heappop(priorityQ)
        
        if currentDistance > dist[int(currentVertex)]:
            continue
        
        for neighbour, weight in edges[int(currentVertex)]:
            distance = currentDistance + weight
            
            if distance < dist[int(neighbour)]:
                dist[int(neighbour)] = distance
                heapq.heappush(priorityQ, (distance, neighbour))
    
    with open("dijkstra.out","w") as file:
        for i in range(2, n):
            if dist[1] != 1000000000:
                file.write("{} ".format(dist[1]))
            else:
                file.write("0 ")
            del dist[1]
    del file


n=len(edges)
startVertex = '1'

calculate_distances()