上周，乔治先生访问了克罗地亚。由于乔治先生是一位非常重要的人物，当他正在某条街道上行驶时，警察会禁止其他车辆进入该街道。不过，在乔治先生进入该街道之前已经进入的车辆可以继续行驶。

在乔治先生访问期间，卢卡正开着他的卡车在城里送货。但由于部分街道被封闭，他无法按时送达货物，几乎丢了工作。虽然现在已经很晚了，但他想知道自己本可以如何更好地规划他的送货路线，即在乔治先生访问期间，他完成送货所需的最少时间是多少。他知道乔治先生所走的路线。

该城市被建模为路口和连接它们的双向街道。对于每条街道，卢卡知道自己通过它需要多少时间（乔治先生通过该街道也需要相同的时间）。

例如，如果乔治先生在第 10 分钟开始通过某条街道，并且需要 5 分钟才能离开，那么该街道将在第 10、11、12、13 和 14 分钟期间被封闭。卢卡可以在第 9 分钟或更早，或者在第 15 分钟或更晚进入该街道。

编写一个程序，计算如果卢卡在乔治先生出发 $K$ 分钟后开始驾驶，他完成送货所需的最少时间。

输入格式

第一行包含两个整数 $N$ 和 $M$（$2 \le N \le 1000$，$2 \le M \le 10\,000$），分别表示路口的数量和街道的数量。路口从 $1$ 到 $N$ 进行编号。

第二行包含四个整数 $A$、$B$、$K$ 和 $G$（$1 \le A, B \le N$，$0 \le K \le 1000$，$0 \le G \le 1000$）。它们依次为：

• 卢卡出发的路口；
• 卢卡必须到达的路口；
• 乔治先生与卢卡出发时间的差值（卢卡在乔治先生开始其路线整整 $K$ 分钟后，从路口 $A$ 出发）；
• 乔治先生路线上的路口数量。

第三行包含 $G$ 个整数，表示乔治先生将依次访问的路口编号。每对相邻的整数表示他将通过的一条街道。该街道必然存在，且乔治先生最多通过每条街道一次。

接下来的 $M$ 行，每行包含三个整数 $A$、$B$ 和 $L$，表示路口 $A$ 和 $B$ 之间有一条双向街道，通过它需要 $L$ 分钟。$L$ 的范围在 $1$ 到 $1000$ 之间。

输出格式

输出卢卡完成送货所需的最少时间（以分钟为单位）。

样例

输入样例 1

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

输出样例 1

21

输入样例 2

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

输出样例 2

40