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 VT = 1.
K policemen are initially located in K distinct locations denoted by A1, A2, ..., AK. Each policeman has a constant speed of VP = 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 B1, B2, ..., BQ. 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 A1, A2, ..., AK.
Next line contains a single integer Q denoting number of ‘special’ nodes. Next line contains Q distinct space separated integers denoting the locations B1, B2, ..., BQ.
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*
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.
## Input
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 A1, A2, ..., AK.Next line contains a single integer Q denoting number of ‘special’ nodes. Next line contains Q distinct space separated integers denoting the locations B1, B2, ..., BQ.Next line contains two distinct integers S and D denoting the source and destination of the thief.
## Output
For each test case print the minimum time required for thief to escape(if possible). Else, output - 1.*Constraints* 1 ≤ N ≤ 105 M ≤ min(2 * 105, N * (N - 1) / 2) 0 ≤ u, v, S, D, Ai, Bi < N 0 ≤ Y ≤ 109 1 ≤ X, u, v ≤ N 0 ≤ K, Q ≤ N 1 ≤ w ≤ 109
[samples]
## Note
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.
**Definitions**
Let $ G = (V, E) $ be a weighted undirected connected graph with $ |V| = N $ nodes and $ |E| = M $ edges.
Let $ w: E \to \mathbb{R}^+ $ denote the edge weight function.
Let $ S, D \in V $ be the thief’s start and destination nodes.
Let $ V_T = 1 $ be the thief’s constant speed.
Let $ V_P = 1 $ be the base speed of each policeman.
Let $ K \in \mathbb{Z}^+ $ be the number of policemen, with initial positions $ A = \{A_1, A_2, \dots, A_K\} \subseteq V $, all distinct.
Let $ Q \in \mathbb{Z}^+ $ be the number of special nodes $ B = \{B_1, B_2, \dots, B_Q\} \subseteq V $, all distinct.
A policeman may use the power booster **at most once**, and **only if located at a node in $ B $**, doubling their speed to $ 2 $.
**Constraints**
1. $ 1 \le N, M \le 10^5 $
2. Edge weights are positive real numbers.
3. $ 1 \le K \le N $, $ 1 \le Q \le N $, $ S \ne D $, all positions distinct as specified.
**Objective**
Compute the **minimum time $ T^* $** such that the thief can travel from $ S $ to $ D $ along some path $ P $ with total time $ T_P = \text{dist}_G(S, D) $, and for **every possible strategy** the policemen may adopt (including choice of whether/where to use the booster), **at least one policeman** reaches $ D $ **no earlier than** the thief.
That is, find:
$$
T^* = \min_{P: S \to D} \left( \text{length}(P) \right)
\quad \text{such that} \quad
\forall \text{policeman strategies}, \; \min_{i \in [K]} \left( \text{time}_i \right) \ge \text{length}(P)
$$
where $ \text{time}_i $ is the minimum time policeman $ i $ can reach $ D $, possibly using the booster optimally (i.e., choosing whether and where to use it).
If no such path exists (i.e., thief cannot reach $ D $), output $ -1 $.
**Note**: The thief escapes **only if** he arrives at $ D $ **strictly before** all policemen (even if one policeman arrives at the same time, he is caught).
Thus, we require:
$$
T^* < \min_{\text{policeman strategies}} \max_{i \in [K]} \left( \text{min time for policeman } i \text{ to reach } D \right)
$$
But since police act optimally to **catch** the thief, we must compute:
$$
T^* = \min \left\{ t \,\middle|\, \exists \text{ path } P \text{ from } S \to D \text{ of length } t, \text{ and } \forall \text{ choices of booster usage by police}, \; \max_{i \in [K]} \text{time}_i > t \right\}
$$
Equivalently, define $ T_{\text{catch}} = \min_{i \in [K]} \left( \min_{\text{booster usage}} \text{time}_i \right) $ — the **minimum time any policeman can reach $ D $** using optimal booster usage.
Then the thief must reach $ D $ in time **strictly less than** $ T_{\text{catch}} $.
Thus:
Let $ d(u, v) $ be shortest path distance in $ G $.
For each policeman $ i $ at position $ A_i $, define:
$$
t_i = \min \left( d(A_i, D), \min_{b \in B} \left( d(A_i, b) + \frac{d(b, D)}{2} \right) \right)
$$
Then the **best possible time for any policeman to reach $ D $** is:
$$
T_{\text{police}} = \min_{i \in [K]} t_i
$$
Thief’s shortest path time:
$$
T_{\text{thief}} = d(S, D)
$$
Then:
- If $ T_{\text{thief}} = \infty $, output $ -1 $.
- Else, if $ T_{\text{thief}} < T_{\text{police}} $, output $ T_{\text{thief}} $.
- Else, output $ -1 $.
**Final Formal Statement**
$$
\boxed{
T^* =
\begin{cases}
d(S, D) & \text{if } d(S, D) < \min_{i=1}^K \min \left( d(A_i, D), \min_{b \in B} \left( d(A_i, b) + \frac{d(b, D)}{2} \right) \right) \\
-1 & \text{otherwise}
\end{cases}
}
$$