program saddasdasdasd;
type vect=array[1..1000]of integer;
     mat=array[1..1000,1..1000]of integer;
const infinit=maxint;
var d,pre,m,dr:vect;c:mat;
    n,nr_m,cost,i,j,k,x,y,start,dmin,lg,vfmin:integer;
    f,g:text;

procedure initializare;
begin
for i:=1 to n do
 for j:=1 to n do begin c[i,j]:=infinit; c[j,i]:=infinit;end;
for i:=1 to nr_m do begin
                    readln(f,x,y,cost);
                    c[x,y]:=cost;
                    end;
for i:=1 to n do begin d[i]:=c[start,i]; pre[i]:=start;end;
{fillchar(m,n,0);  }
m[start]:=1;pre[start]:=0;
end;

procedure asfalteaza;
begin
for j:=1 to n do
   begin
   dmin:=infinit;
   for i:=1 to n do
     if (m[i]=0)and(dmin>d[i]) then begin
                                    dmin:=d[i];
                                    vfmin:=i;
                                    end;
   m[vfmin]:=1;
   for i:=1 to n do
    if (m[i]=0)and(d[i]>dmin+c[vfmin,i]) then
                                             begin
                                             pre[i]:=vfmin;
                                             d[i]:=dmin+c[vfmin,i];
                                             end;
   end;
end;

procedure afiseaza;
begin
for i:=1 to n do
if i<>start then begin
                 writeln(g,'Costul drumului de cost minim de la ',start,' la ',i,' este: ',d[i]);
                 writeln(g,'Drumul de cost minim:');
                 dr[0]:=i; lg:=0;
                 while pre[dr[lg]]<>0 do
                      begin
                      inc(lg);
                      dr[lg]:=pre[dr[lg-1]];
                      end;
                  for j:=lg downto 0 do write(g,dr[j],' ');
                  writeln(g);
                  end;
end;

begin
assign(f,'dijkstra.in');reset(f);
assign(g,'dijkstra.out');rewrite(g);
readln(f,n,nr_m);start:=1;
initializare;
asfalteaza;
//afiseaza;
for i:=2 to n do
 if d[i]=infinit then write(g,0, ' ')
                 else write(g,d[i],' ');



close(f);close(g);
end.