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

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


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

procedure heapify(x:longint);
  var min,w:longint;
  begin
    min:=x;
    if 2*x<=heapsize then
      if drum[heap[2*x]]<drum[heap[min]] then min:=2*x;
    if 2*x+1<=heapsize then
      if drum[heap[2*x+1]]<drum[heap[min]] then min:=2*x+1;
    if min<>x then
      begin
        w:=heap[min];
        heap[min]:=heap[x];
        heap[x]:=w;
        pos[heap[min]]:=min;
        pos[heap[x]]:=x;
        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^.muchie:=z;
      r^.nod:=y;
      r^.next:=a[x];
      a[x]:=r;
    end;

  heap[1]:=1;
  heapsize:=1;
  pos[1]:=1;

  for i:=2 to n do drum[i]:=-1;

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