var v,p,l,o: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;
procedure merge(p,r:longint);
var q,x,y,z:longint;
begin
   q:=(p+r)div 2;
   if p<q then merge(p,q);
   if q+1<r then merge(q+1,r);
   for i:=p to r do
   begin
   d[i]:=a[i];
   e[i]:=b[i];
   f[i]:=c[i];
   end;
   x:=p;
   y:=p;
   z:=q+1;
   while(y<=q)and(z<=r)do
   if(d[y]<d[z])then begin a[x]:=d[y];
                           b[x]:=e[y];
                           c[x]:=f[y];
                           x:=x+1;
                           y:=y+1;
                     end
                else begin a[x]:=d[z];
                           b[x]:=e[z];
                           c[x]:=f[z];
                           x:=x+1;
                           z:=z+1;
                     end;
   for i:=y to q do
   begin
   a[x]:=d[i];
   b[x]:=e[i];
   c[x]:=f[i];
   x:=x+1;
   end;
   for i:=z to r do
   begin
   a[x]:=d[i];
   b[x]:=e[i];
   c[x]:=f[i];
   x:=x+1;
   end;
end;
begin
   assign(z,'dijkstra.in');
   reset(z);
   readln(z,n,m);
   for i:=1 to m do
   begin
   read(z,a[i],b[i],c[i]);
   o[a[i]]:=o[a[i]]+1;
   end;
   close(z);
   merge(1,m);
   for i:=1 to n do
   begin
   p[i]:=i;
   v[i]:=i;
   l[i]:=1000000000;
   o[i]:=o[i-1]+o[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('0 ')
                      else write(z,l[i],' ');
   end;
   writeln(z);
   close(z);
end.