题目背景

T 先生来 Luka 所在的小镇玩，因为 T 先生是一个大人物，警察会对他将走过的路实行交通管制。

Luka 在镇上是一名送货的卡车司机。但是由于一些路正在进行交通管制，他无法及时交货，还因此差点丢掉了他的工作。

题目描述

Luka 知道 T 先生游玩的路线，并且他想要知道最短的交货时间。

该城市由若干十字路口和连接它们的道路连接，并且 Luka 知道他需要在某条路段上开多长时间（T 先生需要同样的时间以开过该路段）。

例如，如果 T 先生在第 $10$ 分钟进入一条路，并且需要 $5$ 分钟离开这条路，那么该街道将在第 $10 \sim 14$ 分钟时被封锁。Luka可以在第 $9$ 分钟或更早的时候，也可以在第 $15$ 分钟及以后进入该道路。

编写一个程序，计算 Luka 在 T 先生到达城市后 $k$ 分钟开始开车的最短时间。

输入格式

第一行两个正整数 $n, m$，分别表示十字路口数和街道数。 十字路口编号为 $1$ 到 $n$。

第二行四个正整数 $a, b, k, g$，分别表示：

• $a$：Luka 起点的路口。
• $b$：Luka 必须到达的十字路口。
• $k$：T 先生和 Luka 之间的出发时间差。
• $g$：T 先生路上的十字路口数。

第三行 $g$ 个整数，表示 T 先生路上依次经过的十字路口。保证存在对应的街道，每条街道只能走一次。

接下来 $m$ 行，每行三个整数 $a, b, l$，表示在坐标 $(a, b)$ 处有一条街道，开过去的时间为 $l$。

输出格式

一行，输出 Luka 送货需要的最短时间（单位：分）。

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

提示

数据规模及约定

对于 $100\%$ 的数据，$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$。

说明

• 本题满分 $60$ 分。
• 本题默认开启 O2 优化开关。
• 题目译自 COCI2007-2008 CONTEST #6 T4 GEORGE，译者
  https://www.luogu.com.cn/user/219791