type pelem=^elem;
     elem=record
       edge,cost:word;
       next:pelem;
     end;
const nmax=50001;
      inf=maxint;
var fi,fo:text;
    n,m,i,j,v1,v2,c,min,t:longint;
    list:array[1..nmax]of pelem;
    H,poz,D:array[1..nmax]of word;
    p:pelem;

procedure readd;
begin
  assign(fi,'dijkstra.in'); reset(fi);
  read(fi,n,m);
  for i:=1 to m do
    begin
      read(fi,v1,v2,c);
      new(p);
      p^.edge:=v2;
      p^.cost:=c;
      p^.next:=list[v1];
      list[v1]:=p;
    end;
  close(fi);
end;

procedure down(i,n:longint);
var tata,fiu,v:longint;
begin
  v:=H[i]; tata:=i; fiu:=i shl 1;
  while fiu<=n do
    begin
      if fiu<n then
        if D[H[fiu]]>D[H[fiu+1]] then fiu:=fiu+1;
      if D[v]>D[H[fiu]] then
        begin
          H[tata]:=H[fiu];
          poz[H[fiu]]:=tata;
          tata:=fiu;
          fiu:=fiu shl 1;
        end
      else fiu:=n+1;
    end;
  H[tata]:=v;
  poz[v]:=tata;
end;

procedure up(i,n:longint);
var tata,fiu,v,aux:longint;
begin
  fiu:=i; tata:=fiu shr 1;
  while (tata<>0)and(D[H[tata]]>D[H[fiu]]) do
    begin
      aux:=H[fiu];
      H[fiu]:=H[tata];
      poz[H[tata]]:=fiu;
      H[tata]:=aux;
      poz[aux]:=tata;
      fiu:=tata;
      tata:=fiu shr 1;
    end;
end;

procedure create_H;
var p:pelem;
    i:longint;
begin
  for i:=1 to n do
    begin
      H[i]:=i;
      D[i]:=inf;
      poz[i]:=i;
    end;
  D[1]:=inf+1;
  p:=list[1];
  while p<>nil do
    begin
      D[p^.edge]:=p^.cost;
      p:=p^.next;
    end;
end;


procedure dijkstra;
begin
  create_H;
  for i:=n shr 1 downto 1 do
    down(i,n);
  t:=n;
  while t>2 do
    begin
      min:=H[1];
      H[1]:=H[t];
      dec(t);
      down(1,t);
      p:=list[min];
      while p<>nil do
        begin
          if D[p^.edge]>D[min]+p^.cost then
            begin
              D[p^.edge]:=D[min]+p^.cost;
              up(poz[p^.edge],t);
            end;
          p:=p^.next;
        end;
    end;
end;

procedure print;
begin
  assign(fo,'dijkstra.out'); rewrite(fo);
  for i:=2 to n do
    if D[i]=inf then write(fo,0,' ')
                else write(fo,D[i],' ');

  close(fo);
end;

begin
  readd;
  dijkstra;
  print;
end.