题目描述

每年，你的叔叔都会组织一次全家聚会。今年，他决定把聚会地点定在风景如画的代尔夫特。然而，你的家人分散居住在比荷卢各地，因此每个人都必须乘火车前往代尔夫特。

如今火车票价格昂贵，于是叔叔请你找出一种花费最少的购票方案，使所有家人都拥有前往代尔夫特的有效车票。

家人们不愿意绕路：每个人只愿意沿着从其出发车站到代尔夫特的某条最短路线旅行。因此，你在购票时必须满足这一条件。

车票有两种：

个人票

一张连接两个车站的个人票，其价格等于这两个车站之间的最短距离，单位为欧元。

团体票

购买团体票时，需要指定两个车站，并写上任意数量乘客的姓名。只要票面上的所有乘客都同时在场，这张团体票就允许他们共同乘坐这两个车站之间的路段。

团体票对每位乘客收费 $g$ 欧元，与两个车站之间的距离无关。

由于某些奇怪的规定，你总共至多只能购买一张团体票，因此不能把家人分成两个或更多团体。一个人在旅途中可以同时使用个人票和团体票。

请计算，让所有家人都能够沿某条最短路线从各自的出发站到达代尔夫特，最少需要花费多少欧元。

下图展示了样例 2 的最优购票方式。粗实线表示团体票覆盖的路线，彩色虚线表示还需要为各位家人购买的个人票路段。

样例 2 最优购票方案

输入格式

第一行包含四个整数 $n,m,p,g$：

• $2\le n\le 1000$：火车站数量；
• $n-1\le m\le 10^5$：车站之间的连接数量；
• $1\le p\le 100$：家庭成员数量；
• $1\le g\le 10^6$：团体票对每位乘客的价格。

第二行包含 $p$ 个整数 $v_i$：

$$1\le v_i\le n,$$

其中 $v_i$ 表示第 $i$ 位家庭成员的出发车站。多位家庭成员可以从同一个车站出发。

接下来 $m$ 行，每行包含三个整数 $a,b,c$：

$$1\le a,b\le n,\qquad a\ne b,\qquad 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

输出

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

输出

145

样例 3

输入

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

输出

25