const   inf=1 shl 30;
type    adr=^noduri;
        noduri=record val:longint; cost:integer; urm:adr; end;
var     L:array[1..50000] of adr;
        H:array[1..50000] of longint;
        D:array[1..50000] of longint;
        E:array[1..50000] of boolean;
        n,m,i,j,a,b,c,min,poz,cn:longint;
        p:adr;
        f:text;

procedure up(poz:longint);
var t,poz2:longint;
begin
  if poz>1 then
    begin
      poz2:=poz shr 1;
      if D[H[poz]]<D[H[poz2]] then
        begin
          t:=H[poz];
          H[poz]:=H[poz2];
          H[poz2]:=t;
          up(poz2);
        end;
    end;
end;

procedure down(poz:longint);
var t,pmin:longint;
begin
  if poz shl 1<=cn then
    begin
      if D[H[poz shl 1]]<D[H[poz shl 1+1]] then pmin:=poz shl 1
                                           else pmin:=poz shl 1+1;
      if D[H[poz]]>D[H[pmin]] then
        begin
          t:=H[poz];
          H[poz]:=H[pmin];
          H[pmin]:=t;
          down(pmin);
        end;
    end;
end;

begin
  assign(f,'dijkstra.in');
  reset(f);
  readln(f,n,m);
  cn:=n;
  for i:=1 to m do
    begin
      readln(f,a,b,c);
      new(p);
      p^.val:=b; p^.urm:=L[a]; p^.cost:=c;
      L[a]:=p;
    end;
  close(f);
  p:=L[1];
  while p<>nil do
    begin
      D[p^.val]:=p^.cost;
      p:=p^.urm;
    end;
  for i:=1 to n do if D[i]=0 then D[i]:=inf;
  for i:=1 to n do
    begin
      H[i]:=i;
      up(i);
    end;
  E[1]:=true;
  for i:=1 to n-1 do
    begin
      poz:=H[1];
      E[poz]:=true;
      for j:=1 to n do
        if not E[j] then
          begin
            p:=L[poz];
            while (p<>nil) and (p^.val<>j) do p:=p^.urm;
            if p<>nil then
              if D[poz]+p^.cost<D[j] then D[j]:=D[poz]+p^.cost;
          end;
      H[1]:=H[cn];
      dec(cn);
      down(1);
    end;
  assign(f,'dijkstra.out');
  rewrite(f);
  for i:=2 to n do if D[i]<inf then write(f,D[i],' ')
                               else write(f,0,' ');
  close(f);
end.