Family Fares

문제

After a long time apart, your family will gather next year for a reunion in an idyllic village in the centre of the country. Since everybody lives apart, most will need to travel by train.

You are in charge of finding the best deal on tickets. Everyone must take an optimal route, that is to say they may only travel a route if no other route is shorter.

Two types of ticket are available: individual or group. All tickets come with a start and destination between which to travel. Individual tickets are unlimited and the price is equal to the shortest distance in kilometres between stations.

Group tickets are more complicated. First, you may only buy at most one and it must be for a set list of people. There is no limit to the number of people named, but all must be present. The ticket is priced according to the number of named persons.

Figure F.1: Sample 2. Group or individual tickets are shown by thick or thin lines, respectively.

입력

• One line with four integers: $nn$ ($2\le n\le 10002\; \backslash le\; n\; \backslash le\; 1000$), the number of stations, $mm$ ($n-1\le m\le {10}^{5}n-1\; \backslash le\; m\; \backslash le\; 10^5$), the number of connections between stations, $pp$ ($1\le p\le 1001\; \backslash le\; p\; \backslash le\; 100$), the number of family members, and $gg$ ($1\le g\le {10}^{6}1\; \backslash le\; g\; \backslash le\; 10^6$), the cost per person of a group ticket.
• One line with $pp$ integers $v_{i}v\_i$ ($1\le v\le n1\; \backslash le\; v\; \backslash le\; n$), meaning that family member $ii$ starts at station $v_{i}v\_i$.
• $mm$ further lines, each with three integers $aa$, $bb$, and $cc$ ($1\le a,b\le n\{1\; \backslash le\; a,b\; \backslash le\; n\}$, $a\mathrm{\ne }ba\backslash neq\; b$, and $1\le c\le {10}^6\{1\; \backslash le\; c\; \backslash le\; 10^6\}$), indicating that there is a bidirectional connection between stations $aa$ and $bb$ with a length of $cc$ kilometres.

Each pair of distinct stations has at most one direct connection and every station can be reached from any other station. Station number $11$ serves the idyllic village.

출력

Output the total amount you must spend so that every family member can travel from their starting station to the idyllic village.

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

35

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

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

25