var i,j,n,m,a,b:longint;
        x0:longint;
    f,g:text;
    c:array[1..50000,1..50000]of integer;
    var min,k,ok:longint;
var viz,d,tata:array[1..50000]of integer;

procedure dijkstra(var x0:longint);
begin
for i:=1 to n do begin
  d[i]:=c[x0,i];
  if d[i]<maxlongint then tata[i]:=x0;
  viz[i]:=0;
end;
  tata[x0]:=0;
  viz[x0]:=1;

for j:=1 to n-1 do begin
   min:=maxlongint;
   for i:=1 to n do
      if (viz[i]=0) and (min>d[i]) and (d[i]>0) then begin
                min:=d[i];
                write(min,' ');
                k:=i;
end;


  viz[k]:=1;
  for i:=1 to n do
  if (viz[i]=0) and (d[i]>d[k]+c[k,i]) then begin
         d[i]:=d[k]+c[k,i];
         tata[i]:=k;
 end;


end;
for i:=2 to n do
write(g,d[i],' ');
end;

begin{pp}
assign(f,'dijkstra.in');reset(f);
assign(g,'dijkstra.out');rewrite(g);
read(f,n,m);
for i:=1 to m do
 for j:=1 to m do
     if i<>j then c[i,j]:=maxint
     else c[i,j]:=0;
for i:=1 to m do
    read(f,a,b,c[a,b]);
x0:=1;
dijkstra(x0);
close(g);

end.