P7192 [COCI 2007/2008 #6] GEORGE

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 送货需要的最短时间（单位：分）。

#### 数据规模及约定 对于 $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](https://hsin.hr/coci/archive/2007_2008/) [CONTEST #6](https://hsin.hr/coci/archive/2007_2008/contest6_tasks.pdf) T4 GEORGE，译者 @[tearing](https://www.luogu.com.cn/user/219791)。