program mindsa;
const fi='dijkstra.in';
      fo='dijkstra.out';
type li=record
nod,val:longint;
end;
var v:array of array of li;
   c,s:array[1..50000] of longint;
  viz:array[1..50000] of longint;
  f,g:text;
  n,m,a,i,b,c1,min,pmin,j,min1,pmin1,min2,pmin2:longint;
  bufin,bufout:array[1..65000] of char;
begin
assign(f,fi);
reset(f);
settextbuf(f,bufin);
assign(g,fo);
rewrite(g);
settextbuf(g,bufout);
read(f,n,m);
setlength(v,n+1);
for i:=1 to m do
  begin
  read(f,a,b,c1);
  if b<>0 then
  begin
  inc(c[a]);
  setlength(v[a],c[a]+1);
  v[a,c[a]].nod:=b;
  v[a,c[a]].val:=c1;
  end;
  end;
for i:=1 to n do
s[i]:=maxlongint;
s[1]:=0;
for i:=1 to c[1] do
    s[v[1,i].nod]:=v[1,i].val;
   viz[1]:=1;
for j:=2 to n do
  begin
  min:=maxlongint-1;
  for i:=1 to n do
      if (viz[i]=0)and(s[i]<min) then
        begin
        if s[i]=min+1 then
          begin
          inc(min);
          pmin:=i;
          break
          end
          else
          begin
        min:=s[i];
        pmin:=i;
        end;
        end;
   viz[pmin]:=1;
  if min>5000000 then break;
  for i:=1 to c[pmin] do
     if s[pmin]+v[pmin,i].val<s[v[pmin,i].nod] then
        begin
        s[v[pmin,i].nod]:=s[pmin]+v[pmin,i].val;
     end;

  end;
  for i:=2 to n do
     begin
     if s[i]=maxlongint then
         write(g,0,' ')
         else

         write(g,s[i],' ');
         end;
close(f);
close(g);
end.