Jimmy is performing in ByteLand today! Anthony the Ant is a huge fan of Jimmy’s music, so he can’t wait to get to the concert.
ByteLand consists of of $N$ intersections and $M$ roads. Every road is bidirectional and connects two distinct intersections. Anthony is currently on intersection $s$ and the concert is being held at intersection $t$. Anthony must get to the concert in $T$ seconds and he can travel at $1$ meter/second.
Unfortunately for Anthony, he has a huge fear of spiders and ByteLand is full of spiders. Spiders reside at certain intersections in ByteLand. Anthony will choose a path from $s$ to $t$ that maximizes $D$, the minimum distance between any intersection on the path and any spider, such that the path can be travelled in no more than $T$ seconds.
The first line contains three integers $N$ ($2\leq N\leq 100\, 000$), $M$ ($1\leq M\leq \min (200\, 000, n(n-1)/2)$), and $T$ ($1\leq T\leq 10^9$).
Each of the next $M$ lines specify the roads. A road is described by three integers $u, v$ ($0\leq u, v\leq N-1$ and $u\neq v$) and $d$ ($1\leq d\leq 10\, 000$), which means that a $d$ meters long road connects intersections $u$ and $v$. It is guaranteed that at most one road connect any two intersections, and that there exists a path between any two intersections.
The next line contains $s, t$ ($0\leq s, t\leq N-1$ and $s\neq t$, representing Anthony’s current location and the location of the concert. You may assume Anthony can always travel from $s$ to $t$ in no more than $T$ seconds.
The last line contains a integer $1\leq K\leq N$, denoting the number of intersections occupied by spiders, followed by $K$ integers $0\leq a_ i\leq N-1$ denoting the intersections with spiders.
Print the maximum $D$ (as defined earlier) for the path Anthony takes.
|Sample Input 1||Sample Output 1|
4 4 3000 0 1 1 1 3 1 2 0 2018 2 3 42 0 3 1 1
|Sample Input 2||Sample Output 2|
4 4 10 0 1 1 1 3 1 2 0 2018 2 3 42 0 3 1 1