가족 운임

오랜 세월 떨어져 지낸 가족이 내년에 나라 중앙에 있는 한적한 마을에 모인다. 가족 모두 따로 살고 있어서 대부분 기차로 이동해야 한다.

당신은 가족이 가장 저렴하게 표를 구하도록 준비하는 역할을 맡았다. 모든 사람은 최적 경로로만 이동해야 하며, 다른 경로보다 짧지 않은 경로만 이용할 수 있다.

표는 개인표와 단체표 두 종류가 있다. 모든 표에는 출발역과 도착역이 정해져 있다. 개인표는 장수 제한이 없고, 가격은 두 역 사이의 최단 거리(km)와 같다.

단체표는 더 복잡하다. 단체표는 최대 한 장만 살 수 있고, 미리 정한 사람 목록에 대한 표여야 한다. 이름을 올릴 수 있는 사람 수에는 제한이 없지만, 이름이 올라간 사람은 모두 함께 있어야 한다. 가격은 이름이 올라간 사람 수에 따라 정해진다.

굵은 선은 단체표, 가는 선은 개인표를 나타낸다.

첫째 줄에 정수 네 개가 주어진다. $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$)는 단체표 1인당 가격이다.

둘째 줄에는 정수 $p$개 $v_i$ ($1 \le v \le n$)가 주어진다. 가족 구성원 $i$가 역 $v_i$에서 출발한다는 뜻이다.

이어지는 $m$개 줄에는 정수 $a$, $b$, $c$ ($1 \le a,b \le n$, $a \neq b$, $1 \le c \le 10^6$)가 주어진다. 역 $a$와 역 $b$ 사이에 길이 $c$ km인 양방향 연결이 있다는 뜻이다.

서로 다른 두 역을 직접 잇는 연결은 최대 하나이며, 모든 역은 다른 모든 역에서 도달할 수 있다. 역 $1$은 한적한 마을에 있는 역이다.

모든 가족 구성원이 출발역에서 마을까지 이동하는 데 필요한 총 금액을 출력한다.