f = File.open("input.txt","r")
(nv,ne)=f.readline.split 
nv=nv.to_i   # кількість вершин
ne=ne.to_i   # кількість ребер
b=[]         # списки суміжності
w=[]         # ваги ребер
c=[]         # ознака сталості
p=[]         # попередники
l=[]         # попередники
l_max=999999 # обмеження зверху на довжину
for k in 0...nv
  b.push([])
  w.push([])
  c.push(false)
  l.push(l_max)
  p.push(0)
end
for i in 0...ne
  (j, k, u)=f.readline.split
  j=j.to_i
  k=k.to_i
  u=u.to_i
  b[j].push(k)
  w[j].push(u)
  b[k].push(j)
  w[k].push(u)
end
f.close

start   = 0           # Номери вершини,
finish  = nv-1 # між якими шукаємо шлях
c[start]=true
l[start]=0
j=start
while (j!=finish)
  for i in 0...b[j].length
    if (!c[b[j][i]])
      s=l[j]+w[j][i]
      if (l[b[j][i]] > s)
          l[b[j][i]] = s
          p[b[j][i]] = j
      end
    end
  end
  s=l_max
  for k in 0...nv
    if (!c[k])
      if (s>l[k])
        s=l[k]
        i=k
      end
    end
  end
  c[i]=true
  j=i
end  

# Запис у вихідний файл
# 1) довжини найкоротшого шляху;
# 2) послідовнисті номерів вершин шляху у зворотньому порядку

f=File.open("output.txt","w")
f.puts l[finish]
f.write(finish)
j=finish
while (j!=start)
  j=p[j]
  f.write(' '+j.to_s)
end
f.write("\n")
f.close()