分组赛的题……madan原题，考试想不出来真是SB得不行
首先，从大往小加边，每次加边如果成环必然弹出环上最大边
考虑询问[x,y]，如果边权在[x,y]的边弹出了小于等于y的边j，说明j不在最小生成树上
其余边权在[x,y]的边都在最小生成树上
因此我们每次只要询问，在一段区间内边权小于等于y的边权和是多少，显然用主席树维护
处理弹出的最大边可以暴力，因为n不大
但我写了lct还是t真是简直了……
const inf=;
type way=record
x,y,z:longint;
end;
node=record
l,r,s:longint;
end; var tree:array[..*] of node;
a:array[..] of way;
h,st,w,f,c,fa,mx:array[..] of longint;
son:array[..,..] of longint;
rev:array[..] of boolean;
ans,j,len,wh,p,i,t,tt,n,m,q,x,y:longint; procedure swap(var a,b:longint);
var c:longint;
begin
c:=a;
a:=b;
b:=c;
end; procedure sort(l,r:longint);
var i,j,x:longint;
y:way;
begin
i:=l;
j:=r;
x:=a[(l+r) shr ].z;
repeat
while a[i].z>x do inc(i);
while x>a[j].z do dec(j);
if not(i>j) then
begin
y:=a[i]; a[i]:=a[j]; a[j]:=y;
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function getf(x:longint):longint;
begin
if f[x]<>x then f[x]:=getf(f[x]);
exit(f[x]);
end; function root(x:longint):boolean;
begin
exit((son[fa[x],]<>x) and (son[fa[x],]<>x));
end; procedure update(x:longint);
var l,r:longint;
begin
l:=son[x,]; r:=son[x,];
mx[x]:=x;
if w[mx[l]]>w[mx[x]] then mx[x]:=mx[l];
if w[mx[r]]>w[mx[x]] then mx[x]:=mx[r];
end; procedure rotate(x,w:longint);
var y:longint;
begin
y:=fa[x];
if not root(y) then
begin
if son[fa[y],]=y then son[fa[y],]:=x
else son[fa[y],]:=x;
end;
fa[x]:=fa[y];
son[y,-w]:=son[x,w];
if son[x,w]<> then fa[son[x,w]]:=y;
son[x,w]:=y;
fa[y]:=x;
update(y);
end; procedure push(x:longint);
begin
if rev[x] then
begin
rev[son[x,]]:=not rev[son[x,]];
rev[son[x,]]:=not rev[son[x,]];
swap(son[x,],son[x,]);
rev[x]:=false;
end;
end; procedure splay(x:longint);
var i,y,t:longint;
fl:boolean;
begin
i:=x;
t:=;
while not root(i) do
begin
inc(t);
st[t]:=i;
i:=fa[i];
end;
inc(t);
st[t]:=i;
for i:=t downto do
push(st[i]);
if t= then exit;
fl:=true;
while fl do
begin
y:=fa[x];
if y=st[t] then
begin
if son[y,]=x then rotate(x,)
else rotate(x,);
fl:=false;
end
else begin
if fa[y]=st[t] then fl:=false;
if son[fa[y],]=y then
begin
if son[y,]=x then rotate(y,)
else rotate(x,);
rotate(x,);
end
else begin
if son[y,]=x then rotate(x,)
else rotate(y,);
rotate(x,);
end;
end;
end;
update(x);
end; procedure access(x:longint);
var y:longint;
begin
y:=;
repeat
splay(x);
son[x,]:=y;
update(x);
y:=x;
x:=fa[x];
until x=;
end; procedure makeroot(x:longint);
begin
access(x);
splay(x);
rev[x]:=not rev[x];
end; procedure link(x,y:longint);
begin
makeroot(x);
fa[x]:=y;
end; procedure cut(x,y:longint);
begin
makeroot(x);
access(y);
splay(y);
son[y,]:=; fa[x]:=;
end; function get(x,y:longint):longint;
begin
makeroot(x);
access(y);
splay(y);
exit(mx[y]);
end; function build(l,r:longint):longint;
var m,q:longint;
begin
inc(t); q:=t;
tree[q].s:=;
if l<>r then
begin
m:=(l+r) shr ;
tree[q].l:=build(l,m);
tree[q].r:=build(m+,r);
end;
exit(q);
end; function add(l,r,last,x,y:longint):longint;
var m,q:longint;
begin
inc(t); q:=t;
if l=r then tree[q].s:=tree[last].s+c[x]*y
else begin
m:=(l+r) shr ;
if x<=m then
begin
tree[q].r:=tree[last].r;
tree[q].l:=add(l,m,tree[last].l,x,y);
end
else begin
tree[q].l:=tree[last].l;
tree[q].r:=add(m+,r,tree[last].r,x,y);
end;
tree[q].s:=tree[tree[q].l].s+tree[tree[q].r].s;
end;
exit(q);
end; function ask(l,r,x,y,k:longint):longint;
var m:longint;
begin
if l=r then
begin
if c[l]<=k then exit(tree[y].s-tree[x].s)
else exit();
end
else begin
m:=(l+r) shr ;
if k<=c[m] then exit(ask(l,m,tree[x].l,tree[y].l,k))
else exit(tree[tree[y].l].s-tree[tree[x].l].s+ask(m+,r,tree[x].r,tree[y].r,k));
end;
end; function find1(l,r,x:longint):longint;
var m:longint;
begin
find1:=r+;
while l<=r do
begin
m:=(l+r) shr ;
if (c[a[m-].z]>x) and (c[a[m].z]<=x) then exit(m);
if c[a[m].z]<=x then r:=m- else l:=m+;
end;
end; function find2(l,r,x:longint):longint;
var m:longint;
begin
find2:=l-;
while l<=r do
begin
m:=(l+r) shr ;
if (c[a[m].z]>=x) and (c[a[m+].z]<x) then exit(m);
if c[a[m].z]>=x then l:=m+ else r:=m-;
end;
end; begin
readln(tt);
while tt> do
begin
dec(tt);
readln(n,m);
for i:= to n+m do
begin
f[i]:=i;
fa[i]:=; son[i,]:=; son[i,]:=;
w[i]:=; rev[i]:=false;
end;
for i:= to m do
readln(a[i].x,a[i].y,a[i].z);
sort(,m);
for i:= to m do
w[n+i]:=a[i].z;
p:=;
c[]:=a[m].z;
a[m].z:=;
for i:=m- downto do
begin
if a[i].z<>c[p] then
begin
inc(p);
c[p]:=a[i].z;
end;
a[i].z:=p;
end;
t:=;
h[]:=build(,p);
for i:= to m do
begin
x:=getf(a[i].x);
y:=getf(a[i].y);
h[i]:=h[i-];
if x<>y then f[x]:=y
else begin
wh:=get(a[i].x,a[i].y);
h[i]:=add(,p,h[i],a[wh-n].z,-);
cut(a[wh-n].x,wh);
cut(a[wh-n].y,wh);
end;
h[i]:=add(,p,h[i],a[i].z,);
link(a[i].x,n+i);
link(a[i].y,n+i);
end;
c[p+]:=inf;
a[].z:=p+;
a[m+].z:=;
c[]:=-;
readln(q);
ans:=;
for i:= to q do
begin
readln(x,y);
x:=x-ans;
y:=y-ans;
len:=y;
if x>y then ans:=
else begin
x:=find2(,m,x);
y:=find1(,m,y);
ans:=ask(,p,h[y-],h[x],len);
end;
writeln(ans);
end;
end;
end.