type matrice=array [1..5000,1..5000]of integer;
     nod=record
          pond,grad,x:longint;
          end;
     tablou=array [1..5000]of nod;
var t:tablou;
    a:matrice;
    i,j,k,m,n,p,q,x,y,min:longint;
    f,g:text;
begin
assign(f,'dijkstra.in');
assign(g,'dijkstra.out');
reset(f);
rewrite(g);
read(f,n,m);
for p:=1 to m do
 begin
  read(f,i,j,k);
  a[i,j]:=k;
 end;
for i:=1 to n do
   t[i].x:=i;
x:=1;
k:=0;
while k<n do
 begin
  for i:=1 to n do
   if (a[x,i]<>0 )and((t[x].pond+a[x,i]<t[i].pond)or(t[i].pond=0))and(t[i].grad<>2) then begin
                                              t[i].pond :=t[x].pond+a[x,i];
                                              t[i].grad:=1;
                                              end;
  t[x].grad:=2;
  k:=k+1;
  i:=1;
  min:=maxint;
  for i:=1 to n do
   if (t[i].grad=1)and(t[i].pond<min) then begin
                                                min:=t[i].pond;
                                                x:=i;
                                            end;

  end;
for i:=2 to n do
  write(g,t[i].pond,' ');
close(f);
close(g);
end.