{$I+}{$N+}                 {Верхні межі:}
const nv_max=2000;     {кількості вершин}
      ne_max=6000;     {кількості ребер }
       l_max=2147483647;  {довжини шляху}
type  pointe=^edge;
      edge=record     {Ребро з вершини:}
      v: word;         {суміжна вершина}
      w: longint;           {вага ребра}
      n: pointe end;    {наступне ребро,
              інцендентне даній вершині}
   pointer=array[0..nv_max] of pointe;
  previous=array[0..nv_max] of word;
    length=array[0..nv_max] of longint;
  constant=array[0..nv_max] of byte;
var  p:^previous; l:^length;  e: pointe;
  n0,n:^pointer;  c:^constant;
   nv,    {Кількість вершин}
   ne,    {Кількість ребер}
    j,    {Номер точки, оголошеної сталою}
start,    {Номери вершини,}
finish,   {між якими шукаємо шлях}
j1,j2: word;         {Кінці ребра}
  w12: longint;       {Вага ребра}
    o: text;

     {Кроки 2-3 алгоритму Дейкстри}
procedure STEP (var j: word);
var k,vmin: word;    stop: boolean;
    s,lmin: longint;
BEGIN
  e:=n0^[j];
  stop:=false;
  REPEAT
    if c^[e^.v]=0 then
    begin
      s:= l^[j]+e^.w;
      if s < l^[e^.v] then
      begin
        l^[e^.v]:=s;
        p^[e^.v]:=j
      end
    end;
    if e^.n <> nil then e:=e^.n
                   else stop:=true;
  UNTIL stop;
            {Пошук вершини j, до якої
  найменша з невстановлених відстаней}
  s:=l_max;
  for k:=0 to nv-1 do
  if (c^[k]=0) then if (s>l^[k]) then
  begin
    s:= l^[k];
    j:=k
  end;
  c^[j]:=1
END;

BEGIN
assign(o,'input.txt');  reset(o);
        {Зчитування рядків вхідного файлу,
       кожний з яких містить трійку чисел:
       номери кінців ребра й вага ребра}
readln(o,nv,ne);
new(n0);
new(n);
for j:=0 to nv-1 do n0^[j]:=nil;
for j:=0 to ne-1 do
begin
  readln(o,j1,j2,w12);
  new(e);
  if n0^[j1]=nil then n0^[j1]   :=e
                 else  n^[j1]^.n:=e;
  n^[j1]:=e;
  e^.v:=j2;
  e^.w:=w12;
  e^.n:=nil;
  new(e);
  if n0^[j2]=nil then n0^[j2]   :=e
                 else  n^[j2]^.n:=e;
  n^[j2]:=e;
  e^.v:=j1;
  e^.w:=w12;
  e^.n:=nil;
end;
close(o);
dispose(n);
new(p);
new(l);
new(c);
for j:=0 to nv-1 do
begin
  l^[j]:=l_max;
  p^[j]:=0;
  c^[j]:=0
end;
start :=0;            {Номери вершини,}
finish:=nv-1; {між якими шукаємо шлях}
c^[start]:=1;
l^[start]:=0;
j:=start;
repeat STEP(j)
 until      j=finish;
                   {Запис у вихідний файл
1) довжини найкоротшого шляху;
2) послідовнисті номерів вершин шляху
   у зворотньому порядку}
assign (o,'output.txt');   rewrite(o);
writeln(o,l^[finish]);
write  (o,finish);
       j:=finish;
repeat j:=p^[j];  write(o,' ',j)
 until j=start;
writeln(o);
close(o)
END.