program distante;
const
pinfinit=maxlongint;
type long=1..50000;
     pnod=^nod;
     nod=record
         nod:long;
         i:1..1000;
         urm:pnod;
         end;
     cheie=record
           val:longint;
           poz:long;
           end;
var a:array[1..50000]of pnod;
    d:array[1..50000]of longint;
    id:array[1..50000]of long;
    s:array[1..50000]of 0..1;
    h:array[1..50000]of cheie;
    i,poz,n,m,dheap,he:longint;
    p:pnod;
    ok:boolean;
    min:longint;
    g:text;
procedure citire;
var z,y,x,i:longint;

 f:text;
begin
assign(f,'dijkstra.in'); reset(f);
read(f,n,m);
for i:=1 to m do begin
 read(f,x,y,z); new(p); p^.nod:=y; p^.i:=z; p^.urm:=a[x]; a[x]:=p;
 if i<=n then d[i]:=pinfinit;
  end;
if n>=m then for i:=n to m do d[i]:=pinfinit;
close(f);
end;
procedure recon_heap(i:longint);
var l,r,max:longint;
    aux:cheie;
begin
l:=i shl 1;
r:=l+1;
if (l<=dheap)and(h[l].val<h[i].val) then max:=l
                        else max:=i;
if (r<=dheap)and(h[r].val<h[max].val) then max:=r;
if max<>i then
          begin

          if ok then begin id[h[max].poz]:=id[h[max].poz] div 2;
                       id[he]:=max;end;
          aux:=h[i]; h[i]:=h[max]; h[max]:=aux;

          recon_heap(max);
          end;
end;
procedure heap;
begin
for i:=n div 2 downto 1 do
  recon_heap(i);
end;
procedure dec_key(i:integer;val:longint);
var aux:cheie;
    a1:longint;
begin
h[i].val:=val;

while (i>1) and (h[i div 2].val>h[i].val) do
begin
aux:=h[i];
 a1:=id[h[i].poz];
 id[h[i].poz]:=id[h[i div 2].poz];
 id[h[i div 2].poz]:=a1;
 h[i]:=h[i div 2]; h[i div 2]:=aux;
i:=i div 2;
end;
end;
begin {pp}
assign(g,'dijkstra.out'); rewrite(g);
citire;
s[1]:=1;
p:=a[1];
while p<>nil do
 begin
 d[p^.nod]:=p^.i;
 p:=p^.urm;
 end;
d[1]:=0;
dheap:=0;
for i:=1 to n do
 if i<>1 then begin
              inc(dheap);
              h[dheap].val:=d[i];
              h[dheap].poz:=i;
              end;
ok:=false;
heap;
for i:=1 to dheap do id[h[i].poz]:=i;
while dheap>0 do
begin
ok:=true;
min:=pinfinit;
poz:=0;
poz:=h[1].poz;
min:=h[1].val;
if min=pinfinit then break;
h[1]:=h[dheap]; id[h[dheap].poz]:=1;
  dec(dheap);
  he:=h[1].poz;
  recon_heap(1);
s[poz]:=1;
p:=a[poz];
while p<>nil do
   begin
if s[p^.nod]=0 then if d[p^.nod]>d[poz]+p^.i then
             begin
           d[p^.nod]:=d[poz]+p^.i;
           dec_key(id[p^.nod],d[p^.nod]);
             end;

   p:=p^.urm;
    end;
end;
for i:=2 to n do if d[i]<>pinfinit then write(g,d[i],' ')
                                   else write(g,0,' ');

close(g);
end.