L. Maze Chase
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Annoyed at sorting stuff for Sultan Malik, advisor Fankoush has stolen a powerful treasure and escaped into a deep maze. He will be taking some specific path that will lead him to a point of no return, where he will disappear without a trace.

The maze contains $$$N$$$ rooms. Each room is connected to one or multiple rooms by a passage. There are $$$M$$$ passages in the maze. Passage $$$i$$$ has length $$$w_i$$$.

The sultan's soldiers chase the thief, and each of them starts in some room in the maze. The soldiers know the exact path that Fankoush will take and the distances between the rooms.

Note the following:

  • The soldiers and the advisor Fankoush do not necessarily have the same speed.
  • All the soldiers have the same constant speed.
  • The time needed to traverse a path of length $$$l$$$ is $$$l / \text{speed}$$$.
  • If Fankoush reaches a room $$$x$$$ at time $$$t_1$$$, and one of the soldiers reaches the same room $$$x$$$ at time $$$t_2$$$, they will be able to catch him if $$$t_2 \leq t_1$$$.

The soldiers' mission is to catch Fankoush before he leaves the maze and escapes forever.

Your task is to help them find the number of the first room where they can intercept him. If it's impossible to catch him in time, you should return $$$-1$$$.

Input
  • The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^5, 0 \leq m \leq 10^5)$$$, representing the number of rooms and passages. Rooms are numbered $$$0$$$ to $$$n-1$$$.
  • Then, $$$m$$$ lines describing the passages of the graph, each $$$i$$$-th line contains three integers $$$u_i, v_i$$$ and $$$w_i$$$, representing an undirected edge between rooms $$$u_i$$$ and $$$v_i$$$ with weight $$$w_i$$$ $$$(distance)$$$ $$$(1 \leq w_i \leq 10^5)$$$.
  • The next line contains an integer $$$k$$$ $$$(1 \leq k \leq 10^5)$$$ followed by $$$k$$$ distinct rooms $$$(0$$$ to $$$n-1)$$$, representing Fankoush's path. The last one is the room before Fankoush leaves the maze forever.
  • The following line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ followed by $$$t$$$ integers $$$(0$$$ to $$$n-1)$$$, representing each soldier's position.
  • The last line contains two integers $$$s_1$$$ and $$$s_2$$$ $$$(1 \leq s_1, s_2 \leq 10^5)$$$, representing Fankoush's speed and the soldiers' speed, respectively.

Note:

  • The graph may have disconnected components.
  • The path taken by Fankoush is guaranteed to exist in the graph.
  • It is guaranteed that there is a maximum of one edge between any two rooms.
Output

Print a single integer, the number of the first room in Fankoush's path where any soldier can intercept him, or $$$-1$$$ if no interception is possible before the last room.

Example
Input
6 7
0 2 1
0 5 3
1 2 2
1 3 2
1 4 2
1 5 2
2 3 2
3 3 1 5
2 0 2
11 10
Output
5