The King's Visit

A city consists of intersections numbered from 1 to N and M bidirectional roads connecting them. The travel time of each road is given, and both the king and the delivery vehicle need that same amount of time to traverse the road.

The king starts at time 0 and visits intersections in the given order. If the king enters a road at time t and that road takes L minutes to traverse, no other vehicle may enter that road at any time from t up to, but not including, t+L. A vehicle that entered the road before time t may continue normally.

The delivery vehicle starts from intersection A exactly K minutes after the king starts and must reach intersection B. It may have to wait because of road closures. Find the minimum time needed from the delivery vehicle's departure until it reaches the destination.

The first line contains the number of intersections N and the number of roads M. Intersections are numbered from 1 to N. (2 <= N <= 1000, 2 <= M <= 10000)

The second line contains four integers A, B, K, and G. A is the delivery vehicle's starting intersection, B is its destination, K is the time difference between the king's departure and the delivery vehicle's departure, and G is the number of intersections visited by the king. (1 <= A, B <= N, 0 <= K <= 1000, 0 <= G <= 1000)

Next, G integers give the intersections visited by the king in order. A road always exists between every adjacent pair in this sequence, and the king uses each road at most once.

The following M lines each contain three integers U, V, and L. They mean that the road connecting intersections U and V takes L minutes to traverse. L is an integer between 1 and 1000, inclusive.

Print the minimum number of minutes needed for the delivery vehicle to reach intersection B after it starts.