program zht;
var
i,j,m,n,q,x,y,p,qd,zd,min,bh:longint;
b:array[0..5000] of 0..1;
l:array[0..5000,0..5000] of longint;
d:array[0..5000] of longint;

function minn(a,b:longint):longint;
begin
if a>b then minn:=b else minn:=a;
end;

begin
assign(input,'ThefallingofZLX.in');
assign(output,'ThefallingofZLX.out');
reset(input);
rewrite(output);
readln(n,m);

for i:=1 to m do
begin
readln(x,y,p);
if l[x,y]=0 then l[x,y]:=p else l[x,y]:=minn(l[x,y],p);
l[y,x]:=l[x,y];
end;

readln(q);
for j:=1 to q do
begin
fillchar(b,sizeof(b),0);
fillchar(d,sizeof(d),0);
readln(qd,zd);

for i:=1 to n do
d[i]:=l[qd,i];


for i:=1 to n do
if d[i]=0 then d[i]:=maxlongint;

b[qd]:=1;

while d[0]=0 do
begin

min:=maxlongint;
bh:=0;

for i:=1 to n do
if (d[i]<min) and (b[i]=0) then begin bh:=i;min:=d[i];end;


if (bh=0) or (min=maxlongint) then break;
if bh=zd then break;

b[bh]:=1;

for i:=1 to n do
if (b[i]=0) and (d[bh]+l[bh,i]<d[i]) and (l[bh,i]<>0)
 then  d[i]:=d[bh]+l[bh,i];


end;
writeln(d[zd]);

end;
close(input);
close(output);
end.