program distante;
const
pinfinit=maxlongint;
type long=0..50000;
     pnod=^nod;
     nod=record
         nod:long;
         i:0..1000;
         urm:pnod;
         end;
     cheie=record
           val:longint;
           poz:long;
           end;
var a:array[1..50000]of pnod;
    d:array[1..50000]of record
                        d:longint;
                        s:0..1;
                        id:long;
                        end;
    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 begin d[i].s:=0; d[i].d:=pinfinit;end; end;
if n>=m then for i:=n to m do begin d[i].s:=0; d[i].d:=pinfinit;end;
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 d[h[max].poz].id:=d[h[max].poz].id div 2;
                       d[he].id:=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:longint;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:=d[h[i].poz].id;
 d[h[i].poz].id:=d[h[i div 2].poz].id;
 d[h[i div 2].poz].d:=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;
d[1].s:=1;
p:=a[1];
while p<>nil do
 begin
 d[p^.nod].d:=p^.i;
 p:=p^.urm;
 end;
d[1].d:=0;
dheap:=0;
for i:=1 to n do
 if i<>1 then begin
              inc(dheap);
              h[dheap].val:=d[i].d;
              h[dheap].poz:=i;
              end;
ok:=false;
heap;
for i:=1 to dheap do d[h[i].poz].id:=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]; d[h[dheap].poz].id:=1;
  dec(dheap);
  he:=h[1].poz;
  recon_heap(1);
d[poz].s:=1;
p:=a[poz];
while p<>nil do
   begin
if (d[p^.nod].s=0)and(d[p^.nod].d<>pinfinit) then if d[p^.nod].d>d[poz].d+p^.i then
             begin
           d[p^.nod].d:=d[poz].d+p^.i;
           dec_key(d[p^.nod].id,d[p^.nod].d);
             end;

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

close(g);
end.