Problem E
Nature Reserve

In a Nature Reserve and Wildlife 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 supply energy for its operations. There is a communication network consisting of several two-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 broadcast to and installed in all other stations via the communication network.

To save energy, all communication channels are initially in an idle state and 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$ stations.

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 two-way communication channels $M$, the size of the program $L$ (in bytes), and the number of initial stations $S$. The constraints are $1 \leq S \leq N \leq {10}^{4}$, $1 \leq M \leq {10}^{6}$, $M \leq N(N-1)/2$, and $1 \leq L \leq {10}^{6}$.

• The second line contains $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 two-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, output the minimum energy units required to send the Smart Data Analysis program to all stations from the initial $S$ stations.

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