409517: GYM103604 L Uranium

You decided to have your 'La casa de papel' moment - and good for you. The main difference is that, instead of stealing gold, you decided to steal... uranium.

The road from the starting point $$$S$$$ to the destination $$$D$$$ is quite complicated. Luckily, you have a map! On this map, you have $$$N$$$ ($$$1 \leq N \leq 10^5$$$) locations that you can get to, and $$$M$$$ ($$$1 \leq M \leq 2 \times 10^5$$$) paths connecting two locations together. Each of these paths has a length of $$$l_i$$$ ($$$1 \leq l_i \leq 10^9$$$) meters. To make things more exciting, the police knows about your plan and are waiting for you in $$$K$$$ ($$$1 \leq K \leq N$$$) different locations that you know of. They are equipped with uranium detectors.

Keep in mind that the more uranium you have, the farther away it can be detected from. In other words, if you decide to steal $$$x$$$ units of uranium, said quantity will be detectable by any cop who is at most $$$x$$$ units of distance away from you.

Having all of this information, you want to know the maximum quantity of uranium that you can steal without being detected by the police. Furthermore, the adrenaline rush of stealing turned you addicted. Therefore, you do not do steal uranium just once - you do it $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$) times, each time with a different starting and ending point.

The first line of input contains two integers $$$N$$$($$$1 \leq N \leq 10^5$$$), $$$M$$$($$$1\leq M \leq 2 \times 10^5$$$): the number of different locations, the number of roads between these locations.

The next $$$M$$$ lines of input will contain three integers $$$x$$$, $$$y$$$ and $$$l_i(1 \leq l \leq 10^9)$$$ , signifying that there is a road from spot $$$x$$$ to spot $$$y$$$ with a length of $$$l_i$$$ meters. Note that there are no roads going from a city to itself, but there may be multiple roads connecting the same two cities.

The next line of input contains an integer $$$K$$$($$$1 \leq K \leq 10^5$$$): the number of police locations.

The following line will contain $$$K$$$ integers $$$P_i$$$, signifying that spot $$$P_i$$$ is being camped by cops.

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

Lastly, there will be $$$Q$$$ lines, each of them representing a query. There will be two integers $$$x$$$, $$$y$$$, signifying that you start your stealing adventure from spot $$$x$$$ and that your destination is spot $$$y$$$.

For every query, print on a line an integer $$$x$$$, denoting the maximum amount of uranium that you can 'borrow' without being caught.

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