Background

Mr. T came to visit Luka’s small town. Because Mr. T is an important person, the police will impose traffic control on the roads he will pass through.

Luka is a delivery truck driver in the town. However, because some roads are under traffic control, he cannot deliver on time and almost lost his job.

Problem Description

Luka knows Mr. T’s travel route, and he wants to know the shortest delivery time.

The city consists of several intersections connected by roads, and Luka knows how long it takes to drive through each road segment (Mr. T needs the same amount of time to drive through that segment).

For example, if Mr. T enters a road at minute $10$ and needs $5$ minutes to leave the road, then this street will be closed during minutes $10 \sim 14$. Luka can enter this road at minute $9$ or earlier, or at minute $15$ or later.

Write a program to compute the minimum time Luka needs to drive, assuming Luka starts driving $k$ minutes after Mr. T arrives in the city.

Input Format

The first line contains two positive integers $n, m$, representing the number of intersections and the number of streets. Intersections are numbered from $1$ to $n$.

The second line contains four positive integers $a, b, k, g$, where:

• $a$: the intersection where Luka starts.
• $b$: the intersection Luka must reach.
• $k$: the difference between Mr. T’s departure time and Luka’s departure time.
• $g$: the number of intersections on Mr. T’s route.

The third line contains $g$ integers, representing the intersections on Mr. T’s route in order. It is guaranteed that the corresponding streets exist, and each street is used at most once.

The next $m$ lines each contain three integers $a, b, l$, meaning there is a street between intersections $a$ and $b$, and the travel time along it is $l$.

Output Format

Output one line containing the minimum time (in minutes) Luka needs to complete the delivery.

6 5
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15 

21

8 9
1 5 5 5
1 2 3 4 5
1 2 8
2 7 4
2 3 10
6 7 40
3 6 5
6 8 3
4 8 4
4 5 5
3 4 23 

40

Hint

Constraints

For $100\%$ of the testdata, $2 \le n \le 10^3$, $2 \le m \le 10^4$, $1 \le a, b \le n$, $0 \le k \le 10^3$, $0 \le g \le 10^3$.

Notes

• The full score for this problem is $60$ points.
• This problem enables the O2 optimization switch by default.
• Translated from COCI2007-2008 CONTEST #6 T4 GEORGE, translator:
  https://www.luogu.com.cn/user/219791

Translated by ChatGPT 5