Dona Minhoca

Dona Minhoca gets furious when she hears people say that worms are palindromic animals whose head cannot be told apart from their tail.

Dona Minhoca lives in a cave built from chambers and tunnels. Each tunnel joins two distinct chambers and can be used in both directions. Take distinct chambers $s_1, s_2, \dots, s_n$ with $n \ge 3$ and set $s_{n+1} = s_1$. If $(s_i, s_{i+1})$ is a tunnel for every $1 \le i \le n$, that sequence is a cycle. The cave may contain cycles, but each chamber belongs to at most one cycle. The chambers and the tunnels are narrow. While part of Dona Minhoca's body occupies a chamber or a tunnel, there is no room for her to enter that chamber or that tunnel again.

Some chambers of the cave can be reached from the surface. Dona Minhoca has a map that gives the length of every tunnel and the two chambers it joins, and she knows her own length.

Dona Minhoca wants to enter the cave through a chamber that reaches the surface, travel as short a distance as possible inside the cave, and come out again through the chamber she entered, always moving forward and never backing up. For each query, decide whether such a trip exists, and when it does, report the shortest distance she travels inside the cave.

The first line contains the number of chambers $S$ and the number of tunnels $T$ ($2 \le S \le 10^4$, $1 \le T \le 2S$). The chambers are identified by the integers $1$ through $S$.

Each of the next $T$ lines describes one tunnel with three integers $A$, $B$ and $C$ ($1 \le A < B \le S$, $1 \le C \le 100$). $A$ and $B$ are the two chambers the tunnel joins and $C$ is the length of the tunnel. A chamber is joined by tunnels to at most 100 other chambers, and each pair of chambers is joined by at most one tunnel. The cave is not necessarily connected.

The next line contains the number of queries $Q$ ($1 \le Q \le 100$). Each of the next $Q$ lines describes one query with two integers $X$ and $M$ ($1 \le X \le S$, $1 \le M \le 10^5$), where $X$ is the chamber Dona Minhoca wants to enter through and $M$ is her length.

For each query print one line with a single integer, the shortest distance Dona Minhoca has to travel inside the cave to enter through the chamber given in the query and come out through the same chamber without ever backing up. If entering and coming out without backing up is impossible, print -1.