program dijkstra;
var     st,sf,p,nod,x,y,c,i,j,k,n,m:longint;
        t:array[0..2,1..500000] of longint;
        viz,start,nr,d:array[1..50000] of longint;
        cd:array[1..500000] of longint;
        bufin,bufout:array[1..66000] of byte;
        ok:boolean;

begin
  assign(input,'dijkstra.in'); reset(input);
  assign(output,'dijkstra.out'); rewrite(output);
  settextbuf(input,bufin);
  settextbuf(output,bufout);
  readln(n,m); k:=0;
  for i:=1 to m do
    begin
      readln(x,y,c);
      inc(k);
      t[0,k]:=y;
      t[1,k]:=start[x];
      start[x]:=k;
      t[2,k]:=c;
    end;
  for i:=2 to n do
    d[i]:=maxlongint;
  st:=0; sf:=1; cd[1]:=1; d[1]:=0; ok:=true;
  while st<sf do
    begin
      inc(st);  nod:=cd[st]; p:=start[nod]; viz[nod]:=0;
      while (p<>0) and (ok=true) do
        begin
          if d[nod]+t[2,p]<d[t[0,p]] then
            begin
              d[t[0,p]]:=d[nod]+t[2,p];
              if viz[t[0,p]]=0 then
                begin
                  inc(sf);
                  cd[sf]:=t[0,p];
                  viz[t[0,p]]:=1;
                  nr[t[0,p]]:=nr[t[0,p]]+1;
                end;
            end;
          if nr[t[0,p]]>n-1 then ok:=false;
          p:=t[1,p];
        end;
    end;
  //if ok then
    begin
      for i:=2 to n do
        if d[i]<maxlongint then write(d[i],' ')
        else write(0,' ');
    end;
  close(input); close(output);
end.