program asss;
type mi=record
    nod,cost:longint;
    end;
var f,g:text;
    n,m,i,j,wnod,wcost,pi,ps,x,y,z,nr:longint;
    d,q:array[0..5000005] of longint;
    a:array of array of mi;
begin
  assign(f,'dijkstra.in'); reset(f);
  assign(g,'dijkstra.out'); rewrite(g);
    readln(f,n,m);
    setlength(a,n+1,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;
     pi:=1;
     ps:=1;
     d[1]:=0;
     q[ps]:=1;
     for i:=2 to n do
       d[i]:=maxlongint;
       while ps<=pi do
         begin
           nr:=q[ps];
           ps:=ps+1;
             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;
                   pi:=pi+1;
                   q[pi]:=wnod;
                   end;
               end;
         end;
       for i:=2 to n do
       begin
         if d[i]=maxlongint then
           d[i]:=0;
         write(g,d[i],' ');
       end;
  close(f);
  close(g);
end.