Program dijkstra;
const INF= 999999999;
var M : array[1..2000,1..2000] of integer;
    H,D: array [1..50000] of longint;
    n,i,a,b,c,v,k,aux,p: 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 (k<n)
                                   and (D[H[k*2+1]]<D[H[k*2]]) then fiu:=k*2+1;
                                   if D[H[fiu]]>=D[H[k]] then fiu:=0
                              end;
               if fiu<>0 then begin
                                   swap(H[k],H[fiu]);
                                   k:=fiu;
                              end;
         until fiu=0;
   end;


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


procedure sterge(var n : longint ; k : longint);
  begin
       H[k]:=H[n];
       n:=n-1;
       if (k>1) and (D[k]<D[k div 2]) then ridica(k)
                                      else coboara(k);
  end;

procedure ordoneaza_heap;
var k : longint;
  begin
      for k:=1 to n do coboara(k);
  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);
                        M[a,b]:=c;
                        {M[b,a]:=c;}
                    end;

   for i:=2 to n do D[i]:=INF;
   for i:=1 to n do H[i]:=i;
   while n>0 do begin
                     v:=H[1];
                     sterge(n,1);
                     for i:=1 to aux do
                         if (M[v,i]<>0) then
                            if D[v]+M[v,i]<D[i] then
                                                  begin
                                                     D[i]:=D[v]+M[v,i];
                                                     ordoneaza_heap;
                                                  end;
                 end;

   for i:=2 to aux do write(D[i],' ');
   close(input);
   close(output);
end.