You are given a weighted directed graph some of whose vertices are marked as special vertices. A valid path in it is a path which satisfies the following conditions:
1. For any two adjacent edges x and y on the path, 0.5*weight($$x$$) <= weight($$y$$) <= 2*weight($$x$$)
2. The path contains exactly one special vertex.
Given two vertices $$x$$ and $$y$$, your task is to calculate the minimum cost of a valid path between them.
Input Format
First line: $$n$$ and $$m$$, the number of vertices and the number of edges in the graph.
($$1 \le n \le 10^5$$, $$1 \le m \le 5*10^5$$ )
Next $$m$$ lines contain three integers $$u$$, $$v$$, and $$w$$ representing an edge from vertex $$u$$ to vertex $$v$$, with a weight of e. ($$1 \le u, v \le n$$, $$1 \le w \le 10^9$$)
Next line contains an integer $$k$$ - the number of special vertices. ($$1 \le k \le n$$)
Next line contains $$k$$ distinct integers, the indices of the special vertices. ($$1 \le index \le n$$)
The last line contains the integers $$x$$ and $$y$$, the source and destination vertices.
($$1 \le x, y \le n$$)
Note: Graph can have multiple edges between two vertices.
Output Format
If there is no valid path from $$x$$ to $$y$$ output -1, else output the minimum cost of a valid path from $$x$$ to $$y$$.
In the given sample, it is clear that path 1-3-4 is a valid path with cost 2. Though 1-2-3-4 is also a valid path, but its cost is 3. So, 2 is the minimum cost of a valid path.