Dona Minhoca

Dona Minhoca는 사람들이 지렁이를 머리와 꼬리를 구분할 수 없는 회문 같은 동물이라고 말하는 것을 들으면 화가 난다.

Dona Minhoca는 방과 터널로 이루어진 굴에서 산다. 터널은 서로 다른 두 방을 잇고, 양쪽 방향으로 모두 지날 수 있다. 서로 다른 방 $s_1, s_2, \dots, s_n$ ($n \ge 3$)을 나열하고 $s_{n+1} = s_1$이라고 둘 때 모든 $1 \le i \le n$에 대해 $(s_i, s_{i+1})$이 터널이면, 이 나열을 사이클이라고 한다. 굴에는 사이클이 있을 수 있지만, 각 방은 최대 한 개의 사이클에만 속한다. 방과 터널은 좁다. 그래서 Dona Minhoca의 몸 일부가 어떤 방이나 터널을 차지하고 있는 동안에는 그 방이나 터널에 다시 들어갈 자리가 없다.

굴의 일부 방은 지상과 통한다. Dona Minhoca는 각 터널의 길이와 그 터널이 잇는 두 방이 적힌 지도를 가지고 있고, 자기 몸 길이도 안다.

Dona Minhoca는 지상과 통하는 방으로 굴에 들어가서 굴 안을 가능한 한 짧게 지나고 들어간 방으로 다시 나오려 한다. 이때 항상 앞으로만 움직이고 절대 뒤로 물러나지 않는다. 질의마다 이렇게 들어갔다 나오는 것이 가능한지 판정하고, 가능하면 굴 안에서 지나는 최소 거리를 구하라.

첫째 줄에 방의 수 $S$와 터널의 수 $T$가 주어진다 ($2 \le S \le 10^4$, $1 \le T \le 2S$). 방은 $1$부터 $S$까지의 정수로 구분한다.

다음 $T$개 줄에는 터널 하나를 나타내는 세 정수 $A$, $B$, $C$가 주어진다 ($1 \le A < B \le S$, $1 \le C \le 100$). $A$와 $B$는 그 터널이 잇는 두 방이고, $C$는 터널의 길이다. 한 방은 최대 100개의 다른 방과 터널로 이어지고, 두 방을 잇는 터널은 최대 한 개다. 굴이 하나로 이어져 있다는 보장은 없다.

다음 줄에 질의의 수 $Q$가 주어진다 ($1 \le Q \le 100$). 다음 $Q$개 줄에는 질의 하나를 나타내는 두 정수 $X$와 $M$이 주어진다 ($1 \le X \le S$, $1 \le M \le 10^5$). $X$는 Dona Minhoca가 들어가려는 방이고, $M$은 Dona Minhoca의 몸 길이다.

각 질의마다 한 줄에 정수 하나만 출력한다. Dona Minhoca가 뒤로 물러나지 않고 질의로 주어진 방으로 들어가서 같은 방으로 나오기 위해 굴 안에서 지나야 하는 최소 거리를 출력한다. 뒤로 물러나지 않고 들어갔다 나오는 것이 불가능하면 -1을 출력한다.