404769: GYM101628 F Find the Inn

On holidays, Bolado decided to go on an adventure. Bored with the urban life, he decided to travel to the mountains, where he'd have the time to discover new places and think in jokes. Upon his arrival, Bolado found himself surrounded by avast and dense forest, with trees of various types, which make his instincts lead him to the following thought.

"Why does the pine tree never gets lost in the woods?"

"Because he has a pine cone!"

(Read the statement in Portuguese to understand the joke)

Glad with the joke he made, Bolado could only think about it while looking for the inn. However, it didn't take too long until our beloved jokester noticed he was lost. Fortunately, he had a map of the area.

In the map there are N areas, numbered from 1 to N. Bolado is currently lost in the area 1 and the inn is in area N. There's also M directional paths which connect two distinct areas. Each path has also a description containing the time in minutes needed to cross it.

Additionally, because environmental preservation matters, P of the N areas have a pine tree. There are no pine trees in area 1 and area N. Whenever Bolado finds himself in one of these areas, he needs to stop and laugh for K seconds while remembering his master piece. There are T minutes left until the sun sets and Bolado wants to arrive at the inn ASAP (so he can think about inn related jokes).

The first line contains five integers, N (2 ≤ N ≤ 3 * 10⁴), M (0 ≤ M ≤ 10⁵), T (0 ≤ T ≤ 5 * 10⁷), K (1 ≤ K ≤ 5 * 10⁷), P (0 ≤ P ≤ N - 2), as described above. Then follows P integers p_i (). After, there are M lines describing each path with three integers x_j, y_j and w_j, indicating that Bolado can go from area x_j to area y_j in w_j minutes, for 1 ≤ j ≤ M (x_j ≠ y_j; 1 ≤ x_j, y_j ≤ N and 1 ≤ w_j ≤ 10⁵).

Print the minimum time Bolado can arrive at the inn. If he can't arrive before or at the same time the sun sets, print “-1” without the quotes.

5 7 312 10 2
3 2
1 2 8
4 5 98
3 2 12
5 2 30
5 1 103
3 4 65
2 3 1

10340

4 6 29370 22446 1
3
4 2 32014
2 3 24
2 1 67
4 3 16
1 2 633
2 4 4298

295860

3 2 701 8561 1
2
2 1 346
3 1 9

-1