uses crt;
type
 op=^elem;
 elem=record
  a,b:longint;
  k:op;
 end;
 lp=array[1..50000] of op;
 pl=array[1..50000] of longint;
var
 v:lp;
 p:op;
 d,r:pl;
 a,b,c,i,j,m,n,min,l,h:longint;
 f,g:text;
begin
 assign(f,'dijkstra.in');
 reset(f);
 assign(g,'dijkstra.out');
 rewrite(g);
 readln(f,n,m);
 for i:=2 to n do
   d[i]:=-1;
 for i:=1 to m do
  begin
   readln(f,a,b,c);
   new(p);
   p^.a:=b;
   p^.b:=c;
   p^.k:=v[a];
   v[a]:=p;
  { new(p);
   p^.a:=a;
   p^.b:=c;
   p^.k:=v[b];
   v[b]:=p;}
   if a=1
    then
      if d[b]=-1
       then  d[b]:=c
       else begin if d[b]>c then begin d[b]:=c;end ;  end
  {  else
     if b=1
      then
       if d[a]=-1
        then d[a]:=c
        else begin if d[a]>c then begin d[a]:=c;end;end;}
  end;
 r[1]:=1;
 for i:=1 to n-1 do
  begin
   j:=2;
   while ((d[j]=-1)or(r[j]=1))and(j<=n) do
     inc(j);
   min:=d[j]; h:=j;
   for l:=j+1 to n do
     if (d[l]<min)and(r[l]<>1)and(d[l]<>-1)
      then
        begin
         h:=l;
         min:=d[l];
        end;
   p:=v[h];   r[h]:=1;
   while p<>nil do
    begin
     if d[p^.a]=-1
      then
        d[p^.a]:=d[h]+p^.b
      else
     if d[p^.a]>d[h]+p^.b
      then d[p^.a]:=d[h]+p^.b;
     p:=p^.k;
    end;
  end;
 for i:=2to n do
  if d[i]=-1
   then write(g,'0 ')
   else write(g,d[i],' ');

 close(f);
 close(g);
end.