Problem M
Toads

Toads in their pipes

There are $N$ Toads in the Mushroom Kingdom, and they have been tasked with building a network of pipes between their houses to facilitate quick travel throughout the kingdom. Each Toad $i$ (numbered from $1$ to $N$) chooses another Toad $j \neq i$ and builds a pipe connecting their houses bidirectionally; this pipe takes $t_ i$ time to cross in either direction. Captain Toad wants all Toads to be able to reach each other quickly enough, so he might build a few additional pipes between various pairs of houses.

After all pipes are built, Captain Toad wants to check how quickly Toads can travel between houses, so he asks you $Q$ queries consisting of two Toads $a$ and $b$. For each query, you must figure out the minimum time required to go from Toad $a$’s house to Toad $b$’s house.

Input

The first line of input contains a single integer $N$ ($2 \leq N \leq 10^5$), the number of Toads.

$N$ lines follow representing each Toad’s pipe. The $i$-th of these lines contains two space-separated integers $j$ ($1 \leq j \leq N$, $j \neq i$) and $t_ i$ ($1 \leq t_ i \leq 10^9$), representing that Toad $i$’s pipe connects their house to Toad $j$’s house and takes $t_ i$ time to cross.

The next line contains a single integer $L$ ($0 \leq L \leq 7$), representing the number of additional pipes built by Captain Toad.

The next $L$ lines each contain three space-separated integers $x,y,t$ ($1 \leq x,y \leq N$, $x \neq y$, $1 \leq t \leq 10^9$), representing a pipe built by Captain Toad between Toad $x$’s house and Toad $y$’s house that takes $t$ time to cross in either direction. It is possible that Captain Toad builds a pipe between two houses that already had a pipe between them (the new pipe may even take longer to cross), but he will not build multiple pipes between the same two houses.

The next line of input contains a single integer $Q$ ($1 \leq Q \leq 10^5$), the number of queries.

Finally, $Q$ lines follow representing each of Captain Toad’s queries. Each line contains two space-separated integers $a$ and $b$ ($1 \leq a,b \leq N$, $a \neq b$), representing the two Toads for each query.

Output

Output $Q$ lines representing the answers to the queries: for each query, output the minimum time required to go from one house to the other, or $-1$ if there is no path between the two houses.

5
3 3
4 2
4 1
5 4
2 7
1
5 3 4
3
1 3
2 5
1 5

3
6
7

6
2 1
3 1
1 1
5 1
6 1
4 1
2
3 4 4
2 6 7
3
1 3
1 4
2 6

1
5
6

6
2 1
3 1
1 1
5 1
6 1
4 1
0
2
1 3
1 4

1
-1