Description
Winning the election was simpler than you expected: it was enough to promise to finally build
a good quality, country-wide road infrastructure, of course without crippling the budget_ Your
happiness did not last long, however: it seems, that the citizens have found a way to actually
hold you accountable for your promise!
There are n major cities in your country. The Ministry of Transport has prepared a detailed
map, outlining m possible highway connections, together with their costs. The Quality Assurance
Committee will not let you build a highway cheaper than l, and the National Spendings
Regulatory Committee will not let you build a highway more expensive than h. To claim a
"country-wide" network, you have to connect (possibly indirectly) as many pairs of cities, as it is
possible within these two constraints. You have to find the cheapest way to do it, and you have
to find it quickly! Of all networks that meet the constraints and connect the most pairs of cities,
compute the cost of the cheapest one.
To make things worse, both committees are heavily influenced by your angry competitors:
each time you publish your hard-prepared plan, they immediatelv change their rulings l and矗，
and vou are forced to start from scratch.
有N个点，M条无向虚边（边还未连接上去），Q组询问，询问格式如下：
对于第一个询问输入2个数L1,H1,表示你要用满足权值L1<=Ai<=H1的所有边来连接点使得能互相通达的点的数量最多。在此条件下，输出最小的权值和C1. 对于第i个询问(1
N<=1000, M<=100000, Q<=1000000
Input
The first line of input contains the number of test cases T. The descriptions of the test cases
follow:
The first line of each test case contains integers n and m (1≤ n≤ 1000; 0≤ rn≤ 100 000) -
the number of cities in the country, and of possible direct connections, respectively.
Each of the following m lines contains three integers x,y,w (1 < x≠ y < n; I≤ w≤
1000 000), denoting that the cities x and y can be connected by a bidirectional highway at cost
w. There might be many ways to connect a single pair of cities.
The following line contains an integer q (1《 q < 1 000 000) - the number of rulings of the
committees. Each of the following q lines contains two integers. The first of the lines contains
the initial rulings 21, hi, given directly. The rest of the rulings are encoded. The numbers in the
j-th of the lines for j > I are lj + Cj_i and hj + cj_i, where lj and hj are the actual rulings and
cj-l is the correct answer for the preceding rulings /j_i and hj_i.
All rulings satisfv I≤ tj≤ hj < 1000 000.
Output
For each test case, output q lines, one for
cost cj of building a highway network which
the maximum number of connected pairs of
each ruling. In the j-th of them, output the minimal
adheres to the committees7 constraints, and creates
cities.
Sample Input
15 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
Sample Output
39
8
14
13
Hint
样例解释：
第一组询问1 2，连接1 2 2和4 5 1两条边，总权值为3.因为没有其他边的权值范围在[1,2]了
第二组询问4 7，实际询问为4-3=1和7-3=4，即[1,4]，最终连接1 2 2, 3 4 3, 4 5 1, 5 1 3, 其余满足条件的边都是冗余的，总权值为9.
以下同理。
