program Dijkstra;
type
  el = record
        x,y:0..50000;
        ut:0..2000;
       end;

var
  be,ki:text;
  rbuf,wbuf:array[1..32000] of byte;
  v:array[1..50000] of longint;
  a:array[1..250000] of el;
  n,m,i:longint;
  kesz:boolean;

begin
 assign(be,'dijkstra.in');
 assign(ki,'dijkstra.out');
 settextbuf(be,rbuf);
 settextbuf(ki,wbuf);
 reset(be);
 rewrite(ki);
 readln(be,n,m);
 for i:=1 to n do v[i]:=10000000;
 for i:=1 to m do
    with a[i] do
     begin
      readln(be,x,y,ut);
      if x=1 then v[y]:=ut;
     end;
 while not kesz do
   begin
     kesz:=true;
     for i:=1 to m do
        with a[i] do
           if v[y] > v[x] + ut then
              begin
               kesz:=false;
               v[y]:=v[x]+ut;
              end;
   end;
 for i:=2 to n do
    if v[i]=10000000 then
       write(ki,'0 ')
      else
       write(ki,v[i],' ');
 close(ki);
end.