题目描述

你是一个小偷，你决定偷点铀来让自己在 Digdig.io 游戏中能够迅速变大。

你有一张地图，这个矿洞是一张 $n$ 个点 $m$ 条边的无向图。有 $K$ 个守卫保护着矿洞的安全，第 $i$ 个守卫守在第 $P_i$ 个点上。

你偷了 $x$ 千克铀，准备选一条路径从 $S$ 点转移到 $T$ 点。如果 $x>0$，那么在转移过程中，你需要保证在任意时刻与每个守卫的距离都大于 $x$。不然就会被发现！

显然，你不会只偷一次，你需要偷 $Q$ 次铀，每次给定 $S$ 和 $T$，询问你最多能偷多少千克的铀。

输入格式

第一行两个数 $n,m$。

接下来 $m$ 行，每一行三个数 $x,y,z$ 表示 $x$ 和 $y$ 有一条长度为 $z$ 的无向边。

下一行一个整数 $K$。接下来一行 $K$ 个整数 $P_i$。

接下来一个正整数 $Q$。紧接着 $Q$ 行每行两个数 $S,T$。

输出格式

$Q$ 行，每行一个数表示答案。如果无法完成偷窃任务输出 $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

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $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$。

说明

翻译自 AGM 2022 Qualification Round L Uranium。