program algoritmul_dijkstra;
  type lista=^celula;
       celula=record
                nod:longint;
                cost:integer;
                next:lista;
              end;
  var f1,f2:text;
      n,m,a,b,c,min,pmin,i,x:longint;
      ad:array [1..50000] of lista;
      r,r2,coada:lista;
      drum:array[1..50000] of longint;

begin
  assign(f1,'dijkstra.in');
  reset(f1);
  assign(f2,'dijkstra.out');
  rewrite(f2);
  readln(f1,n,m);
  for i:=1 to 50000 do begin new(ad[i]);ad[i]^.next:=nil; end;
  for i:= 1 to m do
    begin
      readln(f1,a,b,c);
      new(r);
      r^.nod:=b;
      r^.cost:=c;
      r^.next:=ad[a]^.next;
      ad[a]^.next:=r;
    end;
  for i:=2 to n do drum[i]:=2000000000;
  x:=1; new(coada);
  coada^.next:=nil;
  new(r);
  r^.nod:=1;
  r^.next:=nil;
  coada^.next:=r;
  for i:=1 to n-1 do
    begin
      r:=ad[x]^.next;
      while r<>nil do
        begin
          if drum[x]+r^.cost<drum[r^.nod] then drum[r^.nod]:=drum[x]+r^.cost;
          new(r2);
          r2^.nod:=r^.nod;
          r2^.next:=coada^.next;
          coada^.next:=r2;
          r:=r^.next;
        end;
      r:=coada^.next; min:=2000000000;
      while (r^.next^.nod<>x) do
        begin
          if drum[r^.nod]<min then begin min:=drum[r^.nod]; pmin:=r^.nod; end;
          r:=r^.next;
        end;
      r^.next:=r^.next^.next;
      while r<>nil do
        begin
          if drum[r^.nod]<min then begin min:=drum[r^.nod]; pmin:=r^.nod; end;
          r:=r^.next;
        end;
      x:=pmin;
    end;
  for i:=2 to n do write(f2,drum[i],' ');
  close(f1);
  close(f2);
end.