type lista=^element;
     element=record
                nod,cost:longint;
                a:lista;
             end;
     rec=record
             n,c:longint;
             end;
var n,r,m,j,i,q,w,e,nr:longint;
    d,cc:array[1..50001] of longint;
    viz:array[1..50001] of 0..1;
    c:array[1..50001] of lista;
    p:lista;

procedure reconstituire_heap(i:longint);
     var r,max,s,dd:longint;
     begin
       s:=2*i; dd:=2*i+1;
       max:=i;
       if (s<=m)and(cc[d[s]]<cc[d[i]]) then max:=s;
       if (dd<=m)and(cc[d[dd]]<cc[d[max]]) then max:=dd;
       if max<>i then
          begin
            r:=d[i]; d[i]:=d[max]; d[max]:=r;
            reconstituire_heap(max);
          end;
     end;
procedure creare_heap;
   var t:longint;
   begin
     for  t:=m div 2 downto 1 do
         reconstituire_heap(t);
   end;

begin
assign(input,'dijkstra.in'); reset(input);
assign(output,'dijkstra.out'); rewrite(output);
readln(n,m);
for i:=1 to n do begin viz[i]:=0; cc[i]:=1000000001; d[i]:=i+1;end;
for i:=1 to m do
  begin
    readln(q,w,e);
    new(p);
    p^.nod:=w;
    p^.cost:=e;
    p^.a:=c[q];
    c[q]:=p;
  end;

viz[1]:=1;
p:=c[1];
while p<>nil do     begin   cc[d[p^.nod-1]]:=p^.cost;  p:=p^.a;  end;
m:=n-1;
creare_heap;
nr:=1; viz[1]:=1;
while nr<n do
   begin
     inc(nr);   viz[d[1]]:=1; p:=c[d[1]];
     while p<>nil do
         begin
           if (p^.cost+cc[d[1]]<cc[p^.nod])and(viz[p^.nod]=0) then cc[p^.nod]:=cc[d[1]]+p^.cost;
           p:=p^.a;
         end;
     r:=d[1]; d[1]:=d[m]; d[m]:=r;
     m:=m-1;
     creare_heap;
   end;
for i:=2 to n do if cc[i]=1000000001 then write(0,' ') else write(cc[i],' ');
close(input);
close(output);
end.