program dijkstra;
type natural=record
 nod,cost:longint;
end;
var f,g:text;
    n,m,i,j,nr:longint;
    a:array of array of  natural;
    x,y,z,ps,pi,wnod,wcost:longint;
    sol:array [0..1000005] of longint;
    viz:array[0..1000005]of longint;
    d:array[1..50005] of integer;

begin
 assign (f,'dijkstra.in'); reset (f);
 assign (g,'dijkstra.out'); rewrite (g);
 readln (f,n,m);
 setlength (a,n+1);
 for i:=1 to n do
  setlength (a[i],1);
 for i:=1 to m do
 begin
  readln (f,x,y,z);
  setlength (a[x],length (a[x])+1);
  a[x,0].nod:=a[x,0].nod+1;
  a[x,a[x,0].nod].nod:=y;
  a[x,a[x,0].nod].cost:=z;
 end;
 for i:=1 to n do
  d[i]:=maxint;
 ps:=1; pi:=1;
 sol[ps]:=1; d[1]:=0;
 while ps<=pi do
 begin
  nr:=sol[ps];
  for i:=1 to a[nr,0].nod do
  begin
   wnod:=a[nr,i].nod;
   wcost:=a[nr,i].cost;
   if d[wnod]>d[nr]+wcost then
   begin
    d[wnod]:=d[nr]+wcost;
    viz[wnod]:=1;
    pi:=pi+1;
    sol[pi]:=wnod;
   end;
  end;
  ps:=ps+1;
 end;
 for i:=2 to n do
 begin
  if d[i]=maxint then
   d[i]:=0;
   write (g,d[i], ' ');
 end;
 close (F); close (g);
end.