type lista=^element;
     element=record
               nod,cost:longint;
               a:lista;
            end;
     rec=record
           n,c:longint;
        end;
var n,m,r,i,j,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; c[i]:=nil;
  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;
          reconstituire_heap(d[p^.nod]);
          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.