Program dijkstra;
type lista = ^celula;
     celula = record
                    nod : longint;
                    cost : longint;
                    pred : lista;
               end;
const INF=200000000;
var Lda : array [1..300005] of lista;
    r  :lista;
    H,D: array [1..300051] of longint;
    n,i,a,b,c,v,aux,p,lungime: longint;

procedure  ridica( k : longint);
var aux,aux1 : longint;
    begin
        aux1:=H[k];
        while (k>1) and (D[aux1]<D[H[k div 2]] ) do begin
                                                      aux:=H[k];
                                                      H[k]:=H[k div 2];
                                                      H[k div 2]:=aux;
                                                      k:=k div 2;
                                                    end;
        H[k]:=aux1;

        end;
begin
   assign(input,'dijkstra.in'); reset(input);
   assign(output,'dijkstra.out'); rewrite(output);
   readln(n,p); aux:=n;
   for i:=1 to p do begin
                        readln(a,b,c);
                        new(r);
                        r^.nod:=b;
                        r^.cost:=c;
                        r^.pred:=lda[a];
                        lda[a]:=r;
                    end;

   for i:=2 to n do D[i]:=INF;
   H[1]:=1;
   lungime:=1;
   while lungime>0 do begin
                           v:=H[1];
                           r:=lda[H[1]];
                           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.