The road in ByteLandia – 2#4466
While visiting the islands of ByteLandia, President Bityk realized that the inhabitants also wish to travel around their country using their SonaL vehicles. For this, Bityk must allocate a new budget for constructing two-way bridges. The architect provided the president with the proposed bridge projects. The president must now choose which bridges to build so that all islands are connected. Of course, Bityk wants to spend as little money as possible.
After the bridges are constructed, the islanders are interested in the length of the shortest route between any two islands.
The first line contains two positive integers (1 \leq N \leq 10^5) — the number of islands in the country, and (1 \leq M \leq 10^5) — the number of proposed bridges. Each of the next lines contains three positive integers , , (1 \leq u, v \leq N, u \neq v, 1 \leq w \leq 10^4), meaning that it is possible to build a bridge of length between islands and .
The next line contains a positive integer (1 \leq q \leq 10^7) — the number of queries. Each of the next lines contains two island numbers. For each query, find the length of the shortest path between the given pair of islands.
On the first line, print the total cost of all new bridges built, or Impossible if it is not possible to build a bridge system such that all islands are connected. If it is possible to build the bridges, then for each of the following lines, output the answer to each query.
Example 1