program dijkstra_cu_bellman_ford;
const nmax=50001;
      inf=maxlongint;
var t:array[0..2,1..250001] of longint;
    start,d,count:array[1..nmax] of longint;
    cd:array[1..400000] of longint;
    bufin,bufout:array[1..250001] of byte;
    viz:array[1..nmax] of 0..1;
    n,m,nr,ok,st,sf,p,i,j,k,cost,nod:longint;
    f,g:text;

procedure dijkstra_optim(x:longint);
var ok:boolean;
begin
  for i:=2 to n do
  d[i]:=inf;
 d[x]:=0; cd[1]:=x; ok:=true;
 st:=1; sf:=1; count[x]:=1;
  while (st<=sf)and(ok) do
   begin
    nod:=cd[st];
    viz[nod]:=0;
    p:=start[nod];
    while (p<>0)and(ok) 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
          count[t[0,p]]:=count[t[0,p]]+1;
          viz[t[0,p]]:=1;
          sf:=sf+1;
          cd[sf]:=t[0,p];
         end;
        if count[t[0,p]]>n-1 then
         ok:=false;
       end;
      p:=t[1,p];
     end;
    st:=st+1;
   end;
end;

begin
 assign(f,'dijkstra.in'); reset(f);
 assign(g,'dijkstra.out'); rewrite(g);
 settextbuf(f,bufin);
 settextbuf(g,bufout);
 readln(f,n,m);
 for k:=1 to m do
  begin
   readln(f,i,j,cost);
   t[0,k]:=j;
   t[1,k]:=start[i];
   t[2,k]:=cost;
   start[i]:=k;
  end;
  dijkstra_optim(1);
  for i:=2 to n do
   if d[i]=inf then
    write(g,0,' ')
   else
    write(g,d[i],' ');
 close(f);
 close(g);
end.