Const nmax=50000;
      inf=MaxLongInt;
Type lista=^elem;
     elem=Record
                v:word;
                c:longint;
                urm:lista;   
          end;   
    mat=Array[1..nmax] Of lista;
Var   
    C:mat;
    P:Array[1..nmax] Of word;   
    D:Array[1..nmax] Of longint;
    S:Array[1..nmax] Of 0..1;   
    i,n,m,x,y:longint;
    f:text;   
    min,ct:longint;
    ok:boolean;   
    q:lista;
Procedure drum(k:word);   
begin  
    If p[k]<>0 then begin
               drum(p[k]);   
               write(k,' ');   
        end;   
end;   
{construirea listelor de adiacenta prin adaugare la inceput}  
Procedure adaug(x,y:word;ct:longint);
var p,q:lista;   
begin  
     If C[x]=nil then begin  
                           new(p);   
                           p^.v:=y;   
                           p^.c:=ct;   
                           p^.urm:=Nil;   
                           C[x]:=p;   
                      end  
                  else begin  
                           {adaug la inceput}  
                           p:=C[x];   
                           new(q);   
                           q^.v:=y;   
                           q^.c:=ct;   
                           q^.urm:=p;   
                           C[x]:=q;   
                       end;   
end;   
BEGIN   
  {citirea matricei costurilor}  
  Assign(f,'dijkstra.in'); Reset(f);   
  Readln(f,n,m);   
  For i:=1 to n do  
       C[i]:=Nil;   
  {citirea muchiilor grafului si a costului asociat}  
  For i:=1 to m do  
      begin  
    Readln(f,x,y,ct);   
        adaug(x,y,ct);   
      end;   
  Close(f);   
  {initializari}  
  For i:=1 to n do  
      begin  
      D[i]:=inf;   
      S[i]:=0;   
      end;   
  {x-varful de plecare}  
  x:=1;   
  {initializare drum care are ca varf de start pe x}  
  q:=C[x];   
  While q<>Nil do  
       begin  
          i:=q^.v;   
      D[i]:=q^.c;   
      p[i]:=x;   
         q:=q^.urm;   
       end;   
  S[x]:=1; P[x]:=0;   
  Repeat   
        Ok:=False;   
        min:=inf;   
    For i:=1 to n do  
        If (S[i]=0) and (D[i]< min) then  
        begin  
            min:=D[i];   
            y:=i;   
            Ok:=True;   
        end;   
    If ok then begin  
           S[y]:=1;   
                   q:=C[y];   
                   { relaxarea }  
                   While q<>Nil do begin  
                         i:=q^.v;   
                         If (S[i]=0)and(D[i]>D[y]+q^.c) then  
                         begin  
                        D[i]:=D[y]+q^.c;   
                        p[i]:=y;   
                         end;   
                         q:=q^.urm;   
                   end;   
       end;   
  Until not ok;   
  {afisarea drumurilor}  
  Assign(f,'dijkstra.out'); Rewrite(f);   
  For i:=1 to n do  
    If i<>x then  
       If D[i]<>inf then  
        begin  
            Drum(i);   
            Write(f,d[i]:0,' ');   
        end;   
  close(f);   
END.