Program dijkstra;
type lista = ^celula;
     celula = record
                    nod : longint;
                    cost : longint;
                    pred : lista;
               end;
const INF=2000000000;
var Lda : array [1..50005] of lista;
    r  :lista;
    H,D,poz: array [1..50051] of longint;
    n,i,a,b,c,v,k,aux,p,lungime: longint;
    b1,b2 : array[0..1 shl 17] of char;

procedure swap(var x,y : longint);
  var aux : longint;
    begin
       aux:=x;
       x:=y;
       y:=aux;
    end;

procedure coboara(k : longint);
  var fiu : longint;
    begin
         repeat
               fiu:=0;
               if k*2<=n then
                  begin
                       fiu:=k*2;
                       if (D[H[k*2+1]]<D[H[k*2]]) and (k*2+1<=n) then fiu:=k*2+1;
                       if D[H[fiu]]>=D[H[k]] then fiu:=0
                  end;
                  if fiu<>0 then begin
                                       swap(poz[H[k]],poz[H[fiu]]);
                                       swap(H[k],H[fiu]);
                                       k:=fiu;
                                 end;
         until fiu=0;
   end;

procedure add (v,c : longint; var p : lista);
  var r : lista;
     begin
        new(r);
        r^.nod:=v;
        r^.cost:=c;
        r^.pred:=p;
        p:=r;
     end;

procedure  ridica( k : longint);
  var aux : longint;
    begin
        if k>1 then
           if  D[H[k]]<D[H[k div 2]] then begin
                                            swap(H[k],H[k div 2]);
                                            poz[H[k]]:=k div 2;
                                            poz[H[k div 2]]:=k;
                                            ridica(k div 2);
                                                end;
        end;

begin
   assign(input,'dijkstra.in'); settextbuf(input,b1); reset(input);
   assign(output,'dijkstra.out'); settextbuf(output,b2); rewrite(output);
   readln(n,p); aux:=n;
   for i:=1 to p do begin
                        readln(a,b,c);
                        add(b,c,lda[a]);
                    end;
   for i:=2 to n do D[i]:=INF;
   H[1]:=1;
   poz[1]:=1;
   lungime:=1;
   while lungime>0 do begin
                           v:=H[1];
                           r:=lda[v];
                           H[1]:=H[lungime];
                     lungime:=lungime-1;
   while r<>nil do begin
                       if D[v]+r^.cost<=D[r^.nod] then
                                                  begin
                            D[r^.nod]:=D[v]+r^.cost;
                            lungime:=lungime+1;
                            H[lungime]:=r^.nod;
                            ridica(lungime);
                                                  end;
                           r:=r^.pred;
                    end;
                   end;
   for i:=2 to aux do
                   if D[i]=INF then write(0,' ')
                               else write(D[i],' ');
   close(output);
end.