import sys import heapq imput = sys.stdin.readline def dijkstra(start, g): INF = float("inf") # distance[i][j] # := チケットを使ってないとき(i=0)、使ったとき(i=1)のj番目まで行くときの最短距離 distance = [[INF]*n for i in range(2)] distance[0][start] = 0 distance[1][start] = 0 cost = 0 #q = [(距離, 現在地, チケットを使っているかどうか)] q = [(0, start, 0)] while q: c, v, is_used = heapq.heappop(q) if is_used == 1: if distance[1][v] < c: continue for cost, t in g[v]: if distance[1][v] + cost < distance[1][t]: distance[1][t] = distance[1][v] + cost heapq.heappush(q, (distance[1][t], t, 1)) else: if distance[0][v] < c: continue for cost, t in g[v]: if distance[0][v] + cost < distance[0][t]: distance[0][t] = distance[0][v] + cost heapq.heappush(q, (distance[0][t], t, 0)) if distance[0][v] < distance[1][t]: distance[1][t] = distance[0][v] heapq.heappush(q, (distance[1][t], t, 1)) return distance n, m = map(int, input().split()) info = tuple(tuple(map(int, input().split())) for i in range(m)) graph = [[] for i in range(n)] for i in range(m): graph[info[i][0] - 1].append((info[i][2], info[i][1] - 1)) graph[info[i][1] - 1].append((info[i][2], info[i][0] - 1)) start = 0 ans = dijkstra(start, graph) for i in range(n): print(ans[0][i] + ans[1][i])