var v,p,l,o,u:array[0..50000]of longint;
    n,i,j,k,m,w,q,t,ad:longint;
    a,b,c,d,e,f:array[0..250000]of longint;
    z:text;
begin
   assign(z,'dijkstra.in');
   reset(z);
   readln(z,n,m);
   for i:=1 to m do
   begin
   read(z,d[i],e[i],f[i]);
   o[d[i]]:=o[d[i]]+1;
   end;
   close(z);
   for i:=1 to n do
   begin
   p[i]:=i;
   v[i]:=i;
   l[i]:=1000000000;
   o[i]:=o[i-1]+o[i];
   u[i]:=o[i-1];
   end;
   for i:=1 to m do
   begin
   u[d[i]]:=u[d[i]]+1;
   a[u[d[i]]]:=d[i];
   b[u[d[i]]]:=e[i];
   c[u[d[i]]]:=f[i];
   end;
   l[1]:=0;
   t:=n+1;
   for j:=1 to n do
   begin
   t:=t-1;
   w:=v[t];
   v[t]:=v[1];
   v[1]:=w;
   p[v[1]]:=1;
   p[v[t]]:=t;
   q:=1;
   ad:=1;
   while((l[v[q]]>l[v[q*2]])or(l[v[q]]>l[v[q*2+1]]))and(q*2<t)and(ad=1)do
   begin
   ad:=0;
   if(l[v[q*2]]>l[v[q*2+1]])and(q*2+1<t)and(l[v[q]]>l[v[q*2+1]])then begin w:=v[q];
                                                      v[q]:=v[q*2+1];
                                                      v[q*2+1]:=w;
                                                      p[v[q]]:=q;
                                                      p[v[q*2+1]]:=q*2+1;
                                                      q:=q*2+1;
                                                      ad:=1;
                                                end
                                         else
   if(l[v[q]]>l[v[q*2]])then begin w:=v[q];
                                   ad:=1;
                                                      v[q]:=v[q*2];
                                                      v[q*2]:=w;
                                                      p[v[q]]:=q;
                                                      p[v[q*2]]:=q*2;
                                                      q:=q*2;
                                                end;
   end;
   for i:=o[v[t]-1]+1 to o[v[t]]do
   if(l[a[i]]+c[i]<l[b[i]])then begin l[b[i]]:=l[a[i]]+c[i];
                                      q:=p[b[i]];
                                      while(l[v[q]]<l[v[q div 2]])and(q>1)do
                                      begin
                                      w:=v[q];
                                      v[q]:=v[q div 2];
                                      v[q div 2]:=w;
                                      p[v[q div 2]]:=q div 2;
                                      p[v[q]]:=q;
                                      q:=q div 2;
                                      end;
                                end;
   end;
   assign(z,'dijkstra.out');
   rewrite(z);
   for i:=2 to n do
   begin
   if l[i]=1000000000 then write(z,'0 ')
                      else write(z,l[i],' ');
   end;
   writeln(z);
   close(z);
end.