401943: GYM100589 K Police Catching Thief

A thief is trying to escape the holds of the police through a city. Let’s assume we represent our city by a weighted undirected connected graph(with no self-loops and multi-edges) with N nodes and M edges.

Thief is currently at vertex numbered S and needs to reach vertex numbered D. Thief moves with constant speed V_T = 1.

K policemen are initially located in K distinct locations denoted by A₁, A₂, ..., A_K. Each policeman has a constant speed of V_P = 1.

To help policemen, a single power booster have been provided to them. This power booster can be availed once from any one of the Q distinct ‘special’ nodes B₁, B₂, ..., B_Q. Property of this power booster being that it doubles the speed of the policeman who avails this power booster.

Note: A policeman can choose not to avail the power booster even if he is at a ‘special’ node.

You have to print the shortest time in which thief can escape the police regardless of whatever path the police might take. If he can’t reach the destination, output  - 1.

First line contains N and M, the number of nodes and number of edges respectively.

Each of the next M lines contain integers u v and w denoting an undirected edge between nodes numbered u and v, w being the weight of the edge. Next line contains a single integer K denoting number of different policemen. Next line contains K space separated integers denoting the distinct locations A₁, A₂, ..., A_K.

Next line contains a single integer Q denoting number of ‘special’ nodes. Next line contains Q distinct space separated integers denoting the locations B₁, B₂, ..., B_Q.

Next line contains two distinct integers S and D denoting the source and destination of the thief.

For each test case print the minimum time required for thief to escape(if possible). Else, output  - 1.

Constraints

• 1  ≤  N  ≤  10⁵
• M  ≤  min(2 * 10⁵, N * (N - 1) / 2)
• 0  ≤  u, v, S, D, A_i, B_i < N
• 0  ≤  Y  ≤  10⁹
• 1  ≤  X, u, v  ≤  N
• 0  ≤  K, Q  ≤  N
• 1  ≤  w  ≤  10⁹

4 4
0 1 2
1 2 4
2 3 10
3 0 2
1
3
1
0
2 1

-1

4 3
0 1 2
1 2 8
1 3 10
2
2 3
2
2 3
0 1

2

Example1:

Police takes the path 3 to 0 to 1 availing the power booster at node 0. Even though both policeman and thief reach the destination at same time, police catches thief.

Example2:

Whichever policeman uses the power booster, thief will be able to escape in 2 seconds.