Program distanta_bellmanford
const inf=maxint;
 type drum=record
         x,y,d:integer;
          end;
       coada=record
         xx,dd:integer;
          end;
  var n,m,i,j,l,r:integer;
   q:array[1..500001] of coada;
   a:array[1..250001] of drum;
   rez:array[1..50001] of integer;
    f,g:text;
begin
 assign(f,'bellmanford.in'); reset(f);
  read(f,n,m);
   for i:=1 to m do
    read(f,a[i].x,a[i].y,a[i].d);
  close(f);
   for i:=2 to n do
    rez[i]:=inf;
     rez[1]:=0;
     l:=1; r:=2;
      q[l].xx:=1; q[l].dd:=0;
         while l<r do
          begin
             for i:=1 to m do
               begin
                if (a[i].x=q[l].xx) and (rez[a[i].y]>q[l].dd+a[i].d) then
                 begin
                 rez[a[i].y]:=q[l].dd+a[i].d;
                 q[r].xx:=a[i].y;
                 q[r].dd:=q[l].dd+a[i].d;
                 inc(r);
                     end;
               end;

          inc(l)
          end;
                      assign(g,'bellmanford.out'); rewrite(g);

      for i:=2 to n do
       write(g,rez[i],' ');
        close(g);
end.