import collections import heapq class Dijkstra(): def __init__(self): self.e = collections.defaultdict(list) def add(self, u, v, d, directed=False): """ #0-indexedでなくてもよいことに注意 #u = from, v = to, d = cost #directed = Trueなら、有向グラフである """ if directed is False: self.e[u].append([v, d]) self.e[v].append([u, d]) else: self.e[u].append([v, d]) def delete(self, u, v): self.e[u] = [_ for _ in self.e[u] if _[0] != v] self.e[v] = [_ for _ in self.e[v] if _[0] != u] def Dijkstra_search(self, s): """ #0-indexedでなくてもよいことに注意 #:param s: 始点 #:return: 始点から各点までの最短経路と最短経路を求めるのに必要なprev """ d = collections.defaultdict(lambda: float('inf')) prev = collections.defaultdict(lambda: None) d[s] = 0 q = [] heapq.heappush(q, (0, s)) v = collections.defaultdict(bool) while len(q): k, u = heapq.heappop(q) if v[u]: continue v[u] = True for uv, ud in self.e[u]: if v[uv]: continue vd = k + ud if d[uv] > vd: d[uv] = vd prev[uv] = u heapq.heappush(q, (vd, uv)) return d, prev def getDijkstraShortestPath(self, start, goal): _, prev = self.Dijkstra_search(start) shortestPath = [] node = goal while node is not None: shortestPath.append(node) node = prev[node] return shortestPath[::-1] N, M = map(int, input().split()) ABC = [list(map(int, input().split())) for i in range(M)] graph1 = Dijkstra()#チケット使用しない graph2 = Dijkstra()#チケット1枚使用(使用後をマイナスで表現) for a,b,c in ABC: graph1.add(a, b, c) graph2.add(a, b, c) graph2.add(a, -b, 0) graph2.add(-a, -b, c) g1,_ = graph1.Dijkstra_search(1) g2,_ = graph2.Dijkstra_search(1) for i in range(1,N+1): print(g1[i]+min(g2[-i],g1[i]))