program dijkstra;
  type lista=^celula;
       celula=record
                vecin:longint;
                valoare:longint;
                next:lista;
              end;
       rec=record
             muchie,nod,vecin:longint;
           end;

  var bufin,bufout:array [1..100000] of byte;
      n,m,i,heapsize,vec,x,y,z:longint;
      a:array [1..50000] of lista;
      r,q:lista;
      drum:array[1..50000] of longint;
      heap:array[1..500000] of rec;
      bool:boolean;

procedure up(x:longint);
  var w:rec;
  begin
    if x >1 then
    if heap[x div 2].muchie>heap[x].muchie then
      begin
        w:=heap[x];
        heap[x]:=heap[x div 2];
        heap[x div 2]:=w;
        up(x div 2);
      end;
  end;

procedure heapify(x:longint);
   var min:longint;
       w:rec;
   begin
     min:=x;
     if 2*x<=heapsize then
       if heap[2*x].muchie<heap[min].muchie then min:=2*x;
     if 2*x+1<=heapsize then
       if heap[2*x+1].muchie<heap[min].muchie then min:=2*x+1;
     if min<>x then
       begin
         w:=heap[min];
         heap[min]:=heap[x];
         heap[x]:=w;
         heapify(min);
       end;
   end;

begin
  assign(input,'dijkstra.in');
  reset(input);
  settextbuf(input,bufin);
  assign(output,'dijkstra.out');
  rewrite(output);
  settextbuf(output,bufout);

  readln(n,m);
  for i:=1 to m do
    begin
      readln(x,y,z);
      new(r);
      r^.vecin:=y;
      r^.valoare:=z;
      r^.next:=a[x];
      a[x]:=r;
    end;

  for i:=2 to n do drum[i]:=-1;
  q:=a[1];
  while q<>nil do
    begin
      inc(heapsize);
      heap[heapsize].muchie:=q^.valoare;
      heap[heapsize].vecin:=q^.vecin;
      heap[heapsize].nod:=1;
      up(heapsize);
      q:=q^.next;
    end;
  while heapsize>0 do
    begin
      if drum[heap[1].vecin]=-1 then
        begin
          bool:=true;
          vec:=heap[1].vecin;
        end
        else bool:=false;
      if (drum[heap[1].vecin]=-1)or
         (drum[heap[1].nod]+heap[1].muchie<drum[heap[1].vecin]) then
             drum[heap[1].vecin]:=drum[heap[1].nod]+heap[1].muchie;
      heap[1]:=heap[heapsize];
      dec(heapsize);
      heapify(1);
      if bool then
        begin
          q:=a[vec];
          while q<>nil do
            begin
              inc(heapsize);
              heap[heapsize].muchie:=q^.valoare;
              heap[heapsize].vecin:=q^.vecin;
              heap[heapsize].nod:=vec;
              up(heapsize);
              q:=q^.next;
            end;
        end;
    end;
  for i:=2 to n do
    if drum[i]=-1 then write(0,' ') else write(drum[i],' ');
  close(output);
end.