program cgeb;//2139062143
var
	n,m,i,j,k,a,b,l,f1,f2:longint;
	d:char;
	dis:array[1..10000,1..10000] of longint;
	
begin
	assign(input,'dquery.in');	reset(input);
	assign(output,'dquery.out');	rewrite(output);
	fillchar(dis,sizeof(dis),127);
	readln(n,m);
	for i:=1 to m do begin
		readln(f1,f2,l,d);
		dis[f1,f2]:=l;
		dis[f2,f1]:=l;
	end;
	for i:=1 to n do 
		for j:=1 to n do 
			for k:=1 to n do 
				if (dis[i,j]<2139062143) and (dis[k,i]<2139062143) and (dis[k,j]<2139062143)  and (dis[j,i]<2139062143) and (dis[i,k]<2139062143) and (dis[j,k]<2139062143) and  (dis[j,k]>dis[j,i]+dis[i,k]) and (i<>k) and (i<>j) and (j<>k) then dis[j,k]:=dis[j,i]+dis[i,k];
	readln(m);
	for i:=1 to m do begin
		readln(a,b);
		writeln(dis[a,b]);
	end;
	close(input);	close(output);
end.