每年，你的叔叔都会组织一次全家聚会。今年，他决定将聚会地点定在风景如画的代尔夫特（Delft）市。然而，你的家人分散在比荷卢经济联盟（Benelux）的各个不同地方，因此每个人都必须乘火车前往代尔夫特。

如今火车票很贵，所以你的叔叔请你找出最划算的方案，为每个人买到有效的车票。你的家人表示他们不喜欢绕路：他们只想沿着从出发站到代尔夫特的最短路径之一旅行，因此你在买票时必须考虑到这一点。

经过一番快速研究，你发现有两种类型的车票：个人票和团体票。个人票很简单：两站之间的个人票价格等于它们之间以公里为单位的最短距离。团体票则稍微复杂一些。当你购买团体票时，需要指定两个车站以及任意数量的人员名单。只要名单上的所有人都到场，团体票就允许他们在指定的两个车站之间旅行。无论车站之间的距离如何，每人的费用均为 $g$ 欧元。由于奇怪的规定，你总共只能购买一张团体票，因此你不能将家人分成两个或更多的团体。注意，一个人在旅途中可以同时使用个人票和团体票。

为了让所有家庭成员都能买到前往代尔夫特的有效车票，你最少需要花费多少钱？

图 F.1：样例 2 的可视化，展示了为你的家庭成员购买车票的最优方式。粗线表示团体票的轨迹，彩色虚线表示你需要购买的个人票。

输入格式

输入包含：

• 一行包含四个整数：$n$ ($2 \le n \le 1000$)，火车站的数量；$m$ ($n - 1 \le m \le 10^5$)，车站之间的连接数；$p$ ($1 \le p \le 100$)，家庭成员的数量；以及 $g$ ($1 \le g \le 10^6$)，团体票每人的费用。
• 下一行包含 $p$ 个整数 $v_i$ ($1 \le v_i \le n$)，其中第 $i$ 个整数表示第 $i$ 位家庭成员的出发车站。
• 接下来 $m$ 行，每行包含三个整数 $a$、$b$ 和 $c$ ($1 \le a, b \le n, a \neq b$, $1 \le c \le 10^6$)，表示车站 $a$ 和 $b$ 之间存在一条长度为 $c$ 公里的双向连接。

任意两个不同车站之间最多只有一条直接连接，且每个车站都可以从其他任何车站到达。

代尔夫特车站的编号始终为 1。

输出格式

输出使每位家庭成员都能从其出发车站前往代尔夫特所需的最便宜的有效车票总费用。

样例

样例输入 1

6 5 3 10
4 5 6
1 2 10
2 3 10
3 4 10
4 5 2
4 6 3

样例输出 1

35

样例输入 2

7 7 4 10
5 4 4 7
1 2 100
2 3 100
3 4 10
1 5 80
3 5 30
3 6 10
6 7 5

样例输出 2

145

样例输入 3

4 5 2 10
2 4
1 2 20
2 4 5
1 3 20
3 4 5
1 4 30

样例输出 3

25