import heapq N, M = (int(x) for x in input().split()) d = [[] for i in range(N)] rd = [[] for i in range(N)] for i in range(M): u, v, t = (int(x) for x in input().split()) d[u-1].append([v, t]) rd[v-1].append([u, t]) INF = 10**18 dist1, dist2 = [INF]*N, [INF]*N L = [] heapq.heapify(L) heapq.heappush(L, [0, N-1]) dist1[N-1-1] = 0 while L: c, u = heapq.heappop(L) if dist1[u-1] < c: continue for v, t in d[u-1]: if dist1[v-1] > c+t: dist1[v-1] = c+t heapq.heappush(L, [c+t, v]) L = [] heapq.heapify(L) heapq.heappush(L, [0, N]) dist2[N-1] = 0 while L: c, u = heapq.heappop(L) if dist2[u-1] < c: continue for v, t in d[u-1]: if dist2[v-1] > c+t: dist2[v-1] = c+t heapq.heappush(L, [c+t, v]) rdist1, rdist2 = [INF]*N, [INF]*N L = [] heapq.heapify(L) heapq.heappush(L, [0, N-1]) rdist1[N-1-1] = 0 while L: c, u = heapq.heappop(L) if rdist1[u-1] < c: continue for v, t in rd[u-1]: if rdist1[v-1] > c+t: rdist1[v-1] = c+t heapq.heappush(L, [c+t, v]) L = [] heapq.heapify(L) heapq.heappush(L, [0, N]) rdist2[N-1] = 0 while L: c, u = heapq.heappop(L) if rdist2[u-1] < c: continue for v, t in rd[u-1]: if rdist2[v-1] > c+t: rdist2[v-1] = c+t heapq.heappush(L, [c+t, v]) ans = [] for i in range(N-2): res = min(rdist1[i] + dist1[N-1] + dist2[i], rdist2[i] + dist2[N-2] + dist1[i]) ans.append(res if res < INF else -1) for i in ans: print(i)