type lista=^elem;
	 elem=record
	   csp,t:longint;
	   kov:lista;
	 end;
	 adat=record
	   x,ta:longint;
	 end;

const mer=50100;

var f:text;
	v:array[1..mer] of lista;
	szel:array[1..mer] of adat;
	hely,kolt:array[0..mer] of longint;
	n,m,a,b,c,l,cel,k,i:longint;
	q:lista;

procedure betesz(kp,vp,tav:longint);
var p:lista;
begin
 new(p);
 p^.csp:=vp;
 p^.t:=tav;
 p^.kov:=v[kp];
 v[kp]:=p;
end;

begin
 assign(f,'dijkstra.in');
 reset(f);
 readln(f,n,m);
 for i:=1 to m do begin
   readln(f,a,b,c);
   betesz(a,b,c);
 end;
 close(f);

 l:=1;
 cel:=1;
 szel[1].x:=1;
 szel[1].ta:=0;
 while l<=cel do begin
  q:=v[szel[l].x];
  while q<>nil do begin
    k:=hely[q^.csp];
    if k=0 then begin
      inc(cel);
      szel[cel].x:=q^.csp;
      szel[cel].ta:=szel[l].ta+q^.t;
      hely[q^.csp]:=cel;
      kolt[q^.csp]:=szel[l].ta+q^.t;
    end else begin
      if szel[k].ta>szel[l].ta+q^.t then begin
        szel[k].x:=q^.csp;
        szel[k].ta:=szel[l].ta+q^.t;
        hely[q^.csp]:=k;
        kolt[q^.csp]:=szel[l].ta+q^.t;
      end;
    end;
    q:=q^.kov;
  end;
  inc(l);
 end;

 assign(f,'dijkstra.out');
 rewrite(f);
 for i:=2 to n do write(f,kolt[i],' ');
 close(f);

end.