The road in ByteLandia – 2
By visiting islands of ByteLandia the president Bityk understood that the inhabitants of islands also want to travel the country on their SonaL. That is why Bityk needs to allocate a new budget for building two way bridges. The architect gave the president the projects of future bridges. The president need to choose which bridges will be build to connect all islands. It is obvious that Bityk wants to spend as small as possible.
After that the inhabitants of the islands are interested in which is the length of the smallest route between to islands?
Input
In first line will be given two positive integer: N (1 ≤ N ≤ 10^5) – number of islands in country, and M (1 ≤ M ≤ 10^5) –number of bridge projects. In next M lines will be 3 positive integers: u, v, w (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w ≤ 10^4), u, v – numbers of islands, which can be connect by bridge with length w.
In next line positive integer q (1 ≤ q ≤ 10^7) – numbers of queries. In next q lines will be given numbers of islands, between which is requesting to find a smallest distance.
Output
In first line cost of all new bridges, which was built, or "Impossible" (without quotes), if we can’t build a bridge system, that there will be path between any islands. If we can build a bridges, in next q lines output for all queries.