题目描述

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 immediately change their rulings $l$ and $h$,and you are forced to start from scratch.

输入格式

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 \le n \le 1000, 0 \le m \le 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 \le x ≠ y \le n, 1 \le w \le 1 000 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 \le q \le 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 $l_1, h_1$, given directly. The rest of the rulings are encoded. The numbers in the $j-th$ of the lines for $j > 1$ are $l_j + c_{j -1}$ and $h_j + c_{j-1}$, where $l_j$ and $h_j$ are the actual rulings and $c_{j-1}$ is the correct answer for the preceding rulings $l_{j-1}$ and $h_{j-1}$.

All rulings satisfy $1 \le l_j \le h_j \le 1 000 000$.

输出格式

For each test case, output $q$ lines, one for each ruling. In the $j-th$ of them,output the minimal cost $c_j$ of building a highway network which adheres to the committees’ constraints, and creates the maximum number of connected pairs of cities.

题目大意

给定 $n$ 个点 $m$ 条边有边权的无向图，有 $q$ 个询问，每次询问权值在 $[L,R]$ 内的边组成的最小生成森林的权值。

本题强制在线。对于每组测试数据的第 $j\,(j\ge 2)$ 组询问，输入的 $L',R'$ 需要均减去第 $j-1$ 组询问对应的答案后，才可以得到该询问 $L,R$ 实际的值。

数据范围：$n \le 1000, m \le 100000, q \le 1000000$。

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