2016 ACM ICPC Asia Nha Trang Regional Contest Replay

Start

2017-10-15 12:00 UTC

2016 ACM ICPC Asia Nha Trang Regional Contest Replay

End

2017-10-15 17:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -427 days 13:03:12

Time elapsed

5:00:00

Time remaining

0:00:00

Problem G
Nature Reserve

In a Nature Reserve and Whildlife Park, there are $N$ environmental monitoring stations to monitor temperature, atmospheric pressure, humidity, fire, water quality, etc. Each station, labeled from $1$ to $N$, uses solar panels to self-supply energy for its operations. There is a communication network consisting of several 2-way communication channels between pairs of stations. All stations are connected via this communication network.

To process data at each station, the Nature Reserve and Wildlife Park needs to install a Smart Data Analysis program (with the size of $L$ bytes) to all environmental monitoring stations. The program is initially installed directly to $S$ stations, then broadcasted to and installed in all other stations via the communication network.

To save energy, all communication channels are initially in an idle state and its need to be activated to send information. It takes ${E}_{ij}$ energy units to activate the communication channel between station $i$ and station $j$. Once a channel is activated, it takes one energy unit to transmit one byte via this channel.

Your task is to determine the minimum energy units required to send the Smart Data Analysis program to all stations from the initial $S$ station.

Input

The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than $20$. The following lines describe the datasets.

Each dataset is described by the following lines:

  • The first line contains four positive integers: the number of environmental monitoring stations N, the number of 2-way communication channels $M$, the size of the program $L$ (in bytes), and the number of initial stations $S$ $(1 \leq S \leq N \leq {10}^{4}, 1 \leq M \leq {10}^{6}, M \leq \frac{N*(N-1)}{2}, 1 \leq L \leq {10}^{6})$.

  • The second lines contain $S$ positive integer representing the initial $S$ stations.

  • Each of the following $M$ lines contains three positive integers $i, j$ and ${E}_{ij}$ to denote that there is a 2-way communicataion channel between station $i$ and station $j$, and it takes ${E}_{ij}$ energy units to activate this channel $({E}_{ij} \leq {10}^{6})$.

Output

For each data set, write in one line the minimum energy units required to send the Smart Data Analysis program to all stations from the initial $S$ stations.

Sample Input 1 Sample Output 1
1
4 6 10 1
3
1 2 4
1 3 8
1 4 1
2 3 2
2 4 5
3 4 20
37