Problem G
Arachnophobia

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.

Input

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.

Output

Print the maximum $D$ (as defined earlier) for the path Anthony takes.

4 4 3000
0 1 1
1 3 1
2 0 2018
2 3 42
0 3
1 1

1

4 4 10
0 1 1
1 3 1
2 0 2018
2 3 42
0 3
1 1

0