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:array [0..1,1..250000] of longint;
      vis:array[1..50000] of byte;

procedure heapify(x:longint);
  var min,z:longint;
  begin
    min:=x;
    if 2*x<=heapsize then
      if heap[0,2*x]<heap[0,min] then min:=2*x;
    if 2*x+1<=heapsize then
      if heap[0,2*x+1]<heap[0,min] then min:=2*x+1;
    if min<>x then
      begin
        z:=heap[0,x];
        heap[0,x]:=heap[0,min];
        heap[0,min]:=z;
        z:=heap[1,x];
        heap[1,x]:=heap[1,min];
        heap[1,min]:=z;
        heapify(min);
      end;
  end;

procedure up(x:longint);
  var z:longint;
  begin
   if x>1 then
    if heap[0,x]<heap[0,x div 2] then
      begin
        z:=heap[0,x];
        heap[0,x]:=heap[0,x div 2];
        heap[0,x div 2]:=z;
        z:=heap[0,x];
        heap[0,x]:=heap[0,x div 2];
        heap[0,x div 2]:=z;
        up(x div 2);
      end;
  end;

begin
  assign(input,'dijkstra.in');
  reset(input);
  assign(output,'dijkstra.out');
  rewrite(output);
  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;
  heap[0,1]:=0;
  heap[1,1]:=1;
  heapsize:=1;
  while heapsize>0 do
    begin
      if vis[heap[1,1]]=0 then
        begin
          vis[heap[1,1]]:=1;
          r:=a[heap[1,1]];
          while r<> nil do
            begin
              if vis[r^.nod]=0 then
                begin
                  if (drum[r^.nod]=0)or (drum[heap[1,1]]+r^.cost<drum[r^.nod]) then
                    drum[r^.nod]:=drum[heap[1,1]]+r^.cost;
                  inc(heapsize);
                  heap[0,heapsize]:=drum[heap[1,1]]+r^.cost;
                  heap[1,heapsize]:=r^.nod;
                  up(heapsize);
                end;
              r:=r^.next;
            end;
        end;
      heap[0,1]:=heap[0,heapsize];
      heap[1,1]:=heap[1,heapsize];
      dec(heapsize);
      heapify(1);
    end;
  for i:=2 to n do write(drum[i],' ');
  close(output);
end.