program kk;
type ref=^inr;
     inr=record
          nr:longint;
          cost:longint;
          adr:ref;
         end;
var f:text;
    lista,u:array[1..50000] of ref;
    q:ref;
    lung,h,nod,pos:array[1..50000] of longint;
    viz:array[1..50000] of 0..1;
    ies:boolean;
    n,m,i,a,b,c,nc,xx,nrviz,d,nrheap,key,key1,t:longint;

procedure adaug_in_lista(x,y,z:longint);
begin
   new(q);
   q^.nr:=y;
   q^.adr:=nil;
   q^.cost:=z;
   if lista[x]=nil then begin
                          lista[x]:=q;
                          u[x]:=q;
                        end
                   else begin
                         u[x]^.adr:=q;
                         u[x]:=q;

                        end;
end;

procedure sterge_din_heap;
begin
  h[1]:=h[nrheap];
  nod[1]:=nod[nrheap];
  pos[nod[1]]:=1;
  nrheap:=nrheap-1;
  key:=h[1];
  key1:=nod[1];
  d:=1;
  repeat
  ies:=false;

    if 2*d+1<=nrheap then
    if h[2*d]>h[2*d+1] then t:=2*d+1
                       else t:=2*d
              else if 2*d<=nrheap then t:=2*d
                                  else ies:=true;
   if not ies then
    if key>h[t] then begin
                       h[d]:=h[t];
                       nod[d]:=nod[t];
                       pos[nod[d]]:=d;
                       d:=t;
                     end
                else ies:=true;

  until  ies;
  h[d]:=key;
  nod[d]:=key1;
  pos[nod[d]]:=d;
end;

procedure modific_heap(k,val:longint);
begin
  h[pos[k]]:=val;
end;

procedure adaug_in_heap(k,val:longint);
begin
  nrheap:=nrheap+1;
  h[nrheap]:=val;
  nod[nrheap]:=k;
  pos[k]:=nrheap;
  d:=nrheap;
  key:=h[d];
  key1:=nod[d];
  while (d>1)and(key<h[d div 2]) do
     begin
       h[d]:=h[d div 2];
       nod[d]:=nod[d div 2];
       pos[nod[d]]:=d;
       d:=d div 2;
     end;
  h[d]:=key;
  nod[d]:=key1;
  pos[key1]:=d;
end;

procedure dj;
begin
  nrviz:=1;
  nc:=1;
  viz[1]:=1;
  nrheap:=0;
  repeat
     q:=lista[nc];
     while q<>nil do
       begin
         xx:=lung[nc]+q^.cost;
         if xx<lung[q^.nr] then begin
                                  if viz[q^.nr]=0 then
                                   if pos[q^.nr]>0 then modific_heap(q^.nr,xx)
                                                   else adaug_in_heap(q^.nr,xx);
                                  lung[q^.nr]:=xx;

                                end;
         q:=q^.adr;
       end;

     nc:=nod[1];
     pos[nod[1]]:=0;
     viz[nc]:=1;
     sterge_din_heap;
     nrviz:=nrviz+1;
   until nrviz=n;
end;


begin
assign(f,'dijkstra.in');
reset(f);
readln(f,n,m);
for i:=1 to m do
  begin
     readln(f,a,b,c);
     adaug_in_lista(a,b,c);
  end;
lung[1]:=0;
for i:=2 to n do lung[i]:=2140000000;
dj;
close(f);
assign(f,'dijkstra.out');
rewrite(f);
for i:=2 to n do
  if lung[i]<2140000000 then write(f,lung[i],' ')
            else write(f,0,' ');
close(f);
end.