Hide

Problem I
Evacuation

A city specified by a set of districts and bridges is under threat. Initially, each district can reach any other district through some series of bridges.

A tornado has touched down at district $D_1$ and is destroying everything in its way. The latest model suggests the tornado will destroy districts $D_1, \ldots , D_ K$ following the bridges between $(D_ i, D_{i+1})$. Upon reaching district $D_ K$ the model is not accurate enough to precisely determine the tornadoes course.

Given the tornadoes predicted course you must determine the minimum time it would take to travel from your home located in district $H$ to the evacuation shelter located in district $E$. Of course, once the tornado begins travelling down a bridge it becomes unstable disallowing its use; that is, if the tornado arrives at $D_ i$ at time $T_ i$ and is heading towards $D_ j$, the bidirectional bridge $(D_ i, D_ j)$ will no longer be safe to use at any time $T \ge T_ i$, even if you would nearly be finished crossing it.

Due to their size, residing in the same district as the tornado poses no threat.

Input

The first line of input will contain three integers, $N, M, K$, indicating there are $2 \le N \le 10^4$ districts, $N-1 \le M \le \min (10^5, \frac{N(N+1)}{2})$ bridges, and the tornadoes predicted course contains $2 \le K \le N$ districts.

The next line of input contains two integers $1 \le H, E \le N$ indicating the district of your home and the evacuation shelter respectively.

The following $M$ lines contain three integers each, $U_ i, V_ i, T_ i$, indicating there is a bidirectional bridge between districts $1 \le U_ i \le N$ and $1 \le V_ i \le N$ that takes $1 \le T_ i \le 100$ time to cross. There will be at most one bridge between any pair of districts and $U_ i \neq V_ i$ for each bridge.

The final line contains $K$ space separated integers indicating the districts which the tornado is predicted to destroy. All bridges the tornado follows are guaranteed to exist, the tornado crosses each bridge in the same amount of time it would take for you to cross.

Output

Output a single integer indicating the minimum amount of time it will take to reach district $E$ from district $H$ while avoiding all unstable bridges. Output $-1$ if it is impossible to reach $E$ from $H$.

Sample Input 1 Sample Output 1
4 3 4
2 4
1 2 1
2 3 1
3 4 1
1 2 3 4
2
Sample Input 2 Sample Output 2
4 3 2
1 4
1 2 1
2 3 1
3 4 1
2 3
-1
Sample Input 3 Sample Output 3
6 6 3
1 3
1 2 3
2 3 3
1 5 2
5 3 2
4 5 1
5 6 1
4 5 3
6

Please log in to submit a solution to this problem

Log in