program dijkstra;
  type lista=^celula;
       celula=record
                nod:longint;
                cost:longint;
                next:lista;
              end;
 
  var n,m,i,x,y,z:longint;
      drum:array [1..50000]of longint;
      a:array [1..50000] of lista;
      r:lista;
      heapsize:longint;
      heap,pos:array [1..50000] of longint;
      vis:array[1..50000] of byte;
      bufin,bufout:array [1..100000] of byte;
 
procedure heapify(x:longint);
  var min,z: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
        pos[heap[x]]:=min;
        pos[heap[min]]:=x;
        z:=heap[x];
        heap[x]:=heap[min];
        heap[min]:=z;
        heapify(min);
      end;
  end;
 
procedure up(x:longint);
  var z:longint;
  begin
   if x>1 then
    if drum[heap[x]]<drum[heap[x div 2]] then
      begin
        pos[heap[x]]:=x div 2;
        pos[heap[x div 2]]:=x;
        z:=heap[x];
        heap[x]:=heap[x div 2];
        heap[x div 2]:=z;
        up(x div 2);
      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^.nod:=y;
      r^.cost:=z;
      r^.next:=a[x];
      a[x]:=r;
    end;
{  for i:=2 to n do drum[i]:=-1;        }
  heap[1]:=1;
  pos[1]:=1;
  heapsize:=1;
  while heapsize>0 do
    begin
      if vis[heap[1]]=0 then
        begin
          vis[heap[1]]:=1;
          r:=a[heap[1]];
          while r<> nil do
            begin
              if vis[r^.nod]=0 then
                begin
                  if (drum[r^.nod]=0)then
                    begin
                      inc(heapsize);
                      heap[heapsize]:=r^.nod;
                      drum[r^.nod]:=drum[heap[1]]+r^.cost;
                      pos[r^.nod]:=heapsize;
                      up(heapsize);
                    end else
                    begin
                      if (drum[heap[1]]+r^.cost<drum[r^.nod]) then
                        begin
                          drum[r^.nod]:=drum[heap[1]]+r^.cost;
                          up(pos[r^.nod]);
                        end;
                    end;
                end;
              r:=r^.next;
            end;
        end;
      heap[1]:=heap[heapsize];
      dec(heapsize);
      heapify(1);
    end;
  for i:=2 to n do write(drum[i],' ');
  close(output);
end.