4 5
1 2 2
1 3 5
2 3 1
2 4 4
3 4 1

1 2 3 4
4

import heapq
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
    u,v,w=map(int,input().split())
    g[u].append((v,w)); g[v].append((u,w))
dist=[float('inf')]*(n+1); dist[1]=0; prev=[-1]*(n+1)
hp=[(0,1)]
while hp:
    d,node=heapq.heappop(hp)
    if d>dist[node]: continue
    for nxt,w in g[node]:
        nd=d+w
        if nd<dist[nxt]: dist[nxt]=nd; prev[nxt]=node; heapq.heappush(hp,(nd,nxt))
path=[]; cur=n
while cur!=-1: path.append(cur); cur=prev[cur]
print(*path[::-1])
print(dist[n])