import heapq


def read_input():
    """ Read the input from the file and return it. """
    with open("dijkstra.in") as file:
        content = file.read()
        content = content.replace('\n', ' ')
        nums = content.split(' ')
        
        n = int(nums.pop(0))
        m = int(nums.pop(0))
        edges = []
        for i in range(n+1):
            edges.append([])
        for num in range(m):
            edges[int(nums[num*3])].append((int(nums[num*3+1]),int(nums[num*3+2])))
        
        return n, m, edges        


def calculate_distances(graph, startVertex):
    dist = [float("infinity") for i in range(n+1)]
    dist[startVertex] = 0
    
    visited = [0 for i in range(n+1)]
    
    priorityQ = [(0, startVertex)]
    while len(priorityQ):
        currentDistance, currentVertex = heapq.heappop(priorityQ)
        
        if visited[currentVertex]:
            continue
        
        visited[currentVertex] = 1
        
        for neighbour, weight in graph[currentVertex]:
            distance = currentDistance + weight
            
            if distance < dist[neighbour]:
                dist[neighbour] = distance
                heapq.heappush(priorityQ, (distance, neighbour))
    
    with open("dijkstra.out","w") as file:
        for i in range(2, n+1):
            file.write("{} ".format(dist[i]))
    
    # for i in range(2,n+1):
    #     print(dist[i],end=' ')



n, m, edges = read_input()
startNode = 1

calculate_distances(edges, startNode)