Pork barrel

Winning the election was easier than you expected. Promising to finally build a good country-wide highway network, of course without wrecking the budget, was enough. The happiness did not last: the citizens found a way to hold you to that promise.

Your country has $n$ major cities. The Ministry of Transport prepared a detailed map of $m$ possible highway connections together with their costs. The Quality Assurance Committee does not let you build a highway cheaper than $l$, and the National Spendings Regulatory Committee does not let you build a highway more expensive than $h$. To claim a country-wide network, you have to connect, directly or indirectly, as many pairs of cities as these two constraints permit. Among those networks you have to find the cheapest one, 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.

It gets worse. Both committees answer to your competitors, so every time you publish a plan they change the rulings $l$ and $h$, and you start from scratch.

The first line contains the number of test cases $T$. The test cases follow, each in this format.

The first line of a test case contains the number of cities $n$ and the number of possible direct connections $m$. ($1 \le n \le 1\,000$, $0 \le m \le 100\,000$)

Each of the next $m$ lines contains three integers $x$, $y$, $w$. ($1 \le x, y \le n$, $x \ne y$, $1 \le w \le 1\,000\,000$) 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 next line contains the number of rulings of the committees $q$. ($1 \le q \le 1\,000\,000$) Each of the next $q$ lines contains two integers. The first of these lines gives the initial rulings $l_1$, $h_1$ directly. The rest of the rulings are encoded. The numbers in the $j$-th line 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}$, $h_{j-1}$.

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

For each test case, print $q$ lines, one per ruling. In the $j$-th of them, print the minimal cost $c_j$ of a highway network that adheres to the committees' constraints and creates the maximum number of connected pairs of cities.

In the first example the actual rulings are $(1, 2)$, $(1, 4)$, $(2, 3)$, $(3, 5)$ and $(4, 5)$. The cheapest highway networks for them consist of the connections $\{(1, 2), (4, 5)\}$, $\{(2, 1), (1, 5), (5, 4), (4, 3)\}$, $\{(1, 2), (1, 5), (3, 4)\}$, $\{(1, 5), (5, 2), (2, 3), (3, 4)\}$ and $\{(3, 2), (2, 5), (1, 4)\}$, in that order.