Description

从 CTSEU 毕业之后，wwlw 去 CTSEU 附属小学当了校长。为了保证同学们上学准时且安全，他决定开设校车接送同学们上学。

学校附近的城市路网可以用一个 $n$ 个路口 $m$ 条双向道路的连通图表示。每条双向道路连接了两个路口，且有一个时间权重表示综合各种因素之后一辆校车通过该路段所需要的时间。在经过考量之后，wwlw 选择了其中 $w$ 个路口作为校车的上车地点，同学们按时在这些地点等待校车。

但是由于资金问题，学校至多开设 $K$ 条校车线路。每条校车线路都是一条从学校出发，最后回到学校的一条闭合路径。每天早上，所有校车会同时从学校出发，沿着各自的路径运行，接送沿途的同学，最后回到学校。

现在，wwlw 需要你来规划这些线路，使得这些线路覆盖了所有的上车地点，且最晚回来的校车用时要尽可能少。你只需要告诉他最少用时。

Input

第一行四个整数 $n,m,w,K$（$2\le n\le 500,1\le m\le \frac{n(n-1)}{2},1\le w \le \min(n - 1, 14),1\le K\le w$）。

接下来 $m$ 行，每行三个整数 $u,v,c$（$1\le u,v\le n,1\le c\le 10^5,u\neq v$），表示一条双向道路。保证图中无重边，且给出的图是连通图。

接下来一行 $w$ 个整数 $p_1,p_2,\ldots,p_w$（$2\le p_i\le n$），表示选择的路口，保证 $p_1,\ldots,p_w$ 两两不同。

约定一号路口是学校，且保证上车地点不会选定在此处。

Output

输出一行一个整数，表示最少用时。

Samples

5 5 4 1
1 2 1
2 3 2
3 4 3
4 5 4
1 5 5
2 3 4 5

15

5 5 3 2
1 2 2
2 4 2
1 3 100
3 4 1
4 5 3
2 3 5

14

Resources

The 23rd UESTC Programming Contest Preliminary