Luka's Delivery

Luka knows the route taken by Mr. T and wants to determine the shortest delivery time from his starting point. The city is modeled as a set of intersections connected by roads. Both Luka and Mr. T take the same amount of time to traverse any road. When Mr. T is traversing a road, that road remains blocked for Luka. In particular, if Mr. T enters a road at time \(B\) and requires \(d\) minutes to finish it, then the road is blocked during all minutes in the interval \( [B, B+d-1] \). Thus, Luka can enter the road before time \(B\) or only at time \(B+d\) or later.

Initially, Mr. T enters the city at time 0 and follows a known route. Luka, however, starts driving exactly \(k\) minutes after Mr. T enters. Given the map of the city, the travel times of the roads, and Mr. T's route, calculate the minimum delivery time for Luka (i.e. the difference between his arrival time at his destination and his start time).

The city is described by \(n\) intersections and \(m\) bidirectional roads. Luka’s starting point is at intersection 1 and his destination is at intersection \(n\). Mr. T's route is given as a list of intersections; for every consecutive pair of intersections in his route, the corresponding road is blocked for the period during which Mr. T traverses it.

inputFormat

The input is given as follows:

1. The first line contains two integers \(n\) and \(m\) \((2 \le n \le 10^4,\ 1 \le m \le 10^5)\), representing the number of intersections and roads respectively.
2. The second line contains two integers \(k\) and \(L\) \((0 \le k \le 10^9,\ 2 \le L \le n)\), where \(k\) is the delay (in minutes) after Mr. T enters the city when Luka starts driving, and \(L\) is the number of intersections in Mr. T's route.
3. The third line contains \(L\) integers representing the sequence of intersections (by their labels) that Mr. T visits in order.
4. The next \(m\) lines each contain three integers \(u\), \(v\) and \(l\) \((1 \le u, v \le n,\ u \neq v,\ 1 \le l \le 10^3)\) indicating that there is a bidirectional road between intersections \(u\) and \(v\) which takes \(l\) minutes to traverse. It is guaranteed that Mr. T's route uses existing roads (each road is unique and bidirectional).

Luka starts at intersection 1 and his destination is at intersection \(n\).

outputFormat

Output a single integer, which is the minimum time (in minutes) Luka needs for his delivery, calculated as his arrival time at intersection \(n\) minus \(k\) (i.e. the time elapsed after he starts driving).

sample

6 7
3 4
5 3 2 4
1 2 2
2 4 3
1 3 4
3 2 1
5 3 2
2 6 5
4 6 1

7