Imperial roads

The roads of Cubiconia are in bad shape after years without maintenance. Each road connects two different cities $A$ and $B$ and can be traveled in both directions. There is at most one road between a pair of cities, and the existing roads already let anyone travel between any pair of cities. The new emperor raised the taxes again and promised to repair some of the roads, so that Cubiconians can travel between any pair of cities using only repaired roads.

The Department of Public Works has computed the repair cost of every road. It now wants the cheapest set of roads that keeps the emperor's promise. That is not easy, because the emperor wants one particular road to be in the repaired set and has not decided which one. It could be the road between the city of his castle and the city of his daughter's residence, or the road between the city of his summer palace and the only city by the sea. The engineers expect the decision to take a while, so they want the answer for every candidate in advance.

Given the roads of Cubiconia with their repair costs, write a program that answers a set of queries. Each query names one specific road that must be repaired. For that query, report the minimum total repair cost of a set of roads that contains the named road and lets Cubiconians travel between any pair of cities using only repaired roads.

The first line contains two integers $N$ and $R$, the number of cities and the number of roads in Cubiconia ($2 \le N \le 10^5$, $N - 1 \le R \le 2 \times 10^5$). Cities are identified by distinct integers from $1$ to $N$.

Each of the next $R$ lines describes a road with three integers $A$, $B$ and $C$ ($1 \le A < B \le N$, $1 \le C \le 10^4$), meaning that there is a road between cities $A$ and $B$ and that repairing it costs $C$. There is at most one road between a pair of cities, and the given roads let anyone travel between any pair of cities.

The next line contains an integer $Q$, the number of queries ($1 \le Q \le 10^5$). Each of the next $Q$ lines describes a query with two integers $U$ and $V$ ($1 \le U < V \le N$), meaning that the road between cities $U$ and $V$ must be repaired. That road is one of the $R$ roads given in the input. No query is repeated.

Output $Q$ lines. Line $i$ contains one integer, the answer to query $i$: the minimum total repair cost of a set of roads that contains the road named by the query and lets Cubiconians travel between any pair of cities using only repaired roads.