Problem C
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\le N\le 100000$), $M$ ($1\le M\le min(200000,n(n-1)/2)$), and $T$ ($1\le T\le {10}^9$).

Each of the next $M$ lines specify the roads. A road is described by three integers $u,v$ ($0\le u,v\le N-1$ and $u\ne v$) and $d$ ($1\le d\le 10000$), 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\le s,t\le N-1$ and $s\ne 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\le K\le N$, denoting the number of intersections occupied by spiders, followed by $K$ integers $0\le a_i\le 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