import sys
from collections import defaultdict
from queue import PriorityQueue
#algorytm Dijkstry
def Dijkstra(start):
    Q = PriorityQueue()
    visit[start]=1
    Q.put((0,start))

    while not(Q.empty()):
        v=Q.get()
        if not(visit[v[1]]):
            distance[v[1]]=v[0]
            visit[v[1]]=1
        for i in range(len(graph[v[1]])):
            if not(visit[graph[v[1]][i][0]]):
                new=(graph[v[1]][i][1]+v[0],graph[v[1]][i][0])
                Q.put(new)
        
#wczytanie grafu jako lista sąsiedztwa
n, m = input().split()
n = int(n)
m = int(m)
graph = defaultdict(list)
visit = defaultdict(int)
distance = defaultdict(int)

for i in range(m):
    a, b, c = input().split()
    a = int(a) #koniec
    b = int(b) #początek
    c = int(c) #waga
    edge = (a,c)
    graph[b].append(edge)
    
#Główna część
for i in range(n+1):
    distance[i]=-1
    
Dijkstra(1)
	   
for i in range(2,n+1):
    print(distance[i])