program distante;
const
pinfinit=maxlongint;
type long=1..50000;
     pnod=^nod;
     nod=record
         nod:long;
         i:0..1000;
         urm:pnod;
         end;
     cheie=record
           val:longint;
           poz:long;
           end;
     vec=array[1..50000]of long;
var a:array[1..50000]of pnod;
    d:array[1..50000]of record
                        d:longint;
                        s:0..1;
                        end;
    id:^vec;
    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 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: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:=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;
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;
new(id);
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 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);
d[poz].s:=1;
p:=a[poz];
while p<>nil do
   begin
if d[p^.nod].s=0 then if d[p^.nod].d>d[poz].d+p^.i then
             begin
           d[p^.nod].d:=d[poz].d+p^.i;
           dec_key(id^[p^.nod],d[p^.nod].d);
             end;

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

close(g);
end.