Problem Description

You are a thief. You decide to steal some uranium so that you can grow bigger quickly in the game Digdig.io.

You have a map. This mine is an undirected graph with $n$ vertices and $m$ edges. There are $K$ guards protecting the mine. The $i$-th guard stays at vertex $P_i$.

You have stolen $x$ kilograms of uranium, and you plan to choose a path to move from vertex $S$ to vertex $T$. If $x>0$, then during the transfer, you must ensure that at any moment, your distance to every guard is greater than $x$. Otherwise, you will be discovered.

Obviously, you will not steal only once. You need to steal uranium $Q$ times. Each time, given $S$ and $T$, ask for the maximum number of kilograms of uranium you can steal.

Input Format

The first line contains two integers $n,m$.

The next $m$ lines each contain three integers $x,y,z$, meaning there is an undirected edge of length $z$ between $x$ and $y$.

The next line contains an integer $K$. The following line contains $K$ integers $P_i$.

Then comes a positive integer $Q$. The next $Q$ lines each contain two integers $S,T$.

Output Format

Output $Q$ lines, each containing one integer as the answer. If it is impossible to complete the theft task, output $0$.

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

0
1
2

9 10
1 2 1
2 3 4
2 4 2
4 5 5
5 9 10
5 6 10
6 7 2
6 9 5
9 8 8
8 7 3
2
4 9
5
1 3
1 6
5 7
6 9
7 8

1
0
4
0
6

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\leq n,K,Q\leq 10^5$, $1\leq m\leq 2\times 10^5$, $1\leq x,y,P_i\leq n$, $1\leq z\leq 10^9$, and $S\neq T$.

Notes

Translated from AGM 2022 Qualification Round L Uranium。

Translated by ChatGPT 5