题目描述

$n$ 个点 $m$ 条边有边权的无向图，有 $q$ 个询问，每次询问权值在 $[L,R]$ 内的边组成的最小生成树的权值和，强制在线。

输入格式

多组数据，第一行一个整数 $T$ 表示数据组数。

每组数据的第一行为两个整数 $n$ 和 $m$，接下来 $m$ 行，每行三个整数 $x,y,w$ 表示一条边。

然后一行为一个整数 $q$，接下来 $q$ 行，每行两个整数 $L,R$ ,表示一个询问。

输出格式

共 $T$ 行，每行一个整数表示最小生成树的权值和。

1
5 7
1 2 2
2 3 4
3 4 3
4 5 1
5 1 3
2 5 4
1 4 5
5
1 2
4 7
11 12
11 13
18 19

3
9
8
14
13

数据范围

对于 $100\%$ 的数据，$n\le 10^3, m\le 10^5, q\le 10^6$。