题目描述

某重要人物 $P$ 要寻访城市 $C$ 的 $G$ 个地方，由于该人物非常重要，交警打算对人物 $P$ 行走的街道进行临时封道（不准普通市民进入，但如果在封道前进入的可以继续行走，也可以正常出去）。当人物 $P$ 进入这条街道之前和 $P$ 走出这条街道之后，普通市民都可以正常进入该街道。

比如，$P$ 在第 $10$ 分钟期间进入街道 $X$ ，并要 $X$ 街道上行走 $5$ 分钟，则在第 $10$、$11$、$12$、$13$、$14$ 分钟期间，普通市民不可以进入 $X$ 街道，市民可以在第 $9$ 分钟之前（含第 $9$ 分钟）进入，也可以在第 $15$ 分钟之后（含第 $15$ 分钟）进入。

人物 $P$ 寻访 $K$ 分钟后，有一市民 $S$ 打算从城市的 $A$ 处到达 $B$ 处，请编程计算 $P$ 从 $A$ 到 $B$ 的最少用时。注意：市民 $S$ 在行走的过程中某条街道可以走，但为了用更短的时间，可以选择等待！

输入格式

共 $M+3$ 行。

第 $1$ 行 $2$ 个整数 $N$ 和 $M$ ( $2 \le N \le 1000$ , $2 \le M \le 10000$ )，分别表示城市中的结点（即某个地方，从 $1$ 到 $N$ 编号）的数量以及街道的数目。

第 $2$ 行包含 $4$ 个整数 $A$, $B$, $K$ 和 $G$ ( $1 \le A , B \le N$ , $0 \le K \le 1000$ , $0 \le G \le 1000$ )，分别表示：

市民 $S$ 的出发地

市民 $S$ 的目的地

市民 $S$ 是在人物 $P$ 寻访 $K$ 分钟后开始出发

人物 $P$ 寻访的结点（地方）数量

第 $3$ 行 $G$ 个整数，表示人物 $P$ 将要寻访的 $G$ 处地方的编号，每一对结点代表了人物 $P$ 寻访要经过的街道，每条街道仅走一次。

接下来 $M$ 行，每行 $3$ 个整数 $A$, $B$ 和 $L$ ( $1 \le A, B \le N$ , $0 \le L \le 1000$ )，表示 $A$ 和 $B$ 之间有一条需要走 $L$ 分钟的街道（假定人物 $P$ 和市民 $S$ 行走速度相同）。

数据范围

40% 的数据保证 $2 \le N \le 550$ 且 $2 \le M \le 4000$

100% 的数据保证 $2 \le N \le 1000$ 且 $2 \le M \le 10000$

输出格式

一个整数，表示市民 $S$ 从 $A$ 处到达 $B$ 处的最少用时（单位分钟）。

样例

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

20

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