Optimizing Courier Routes for ICPC Secret Projects

The Innovative Consumer Products Company (ICPC) is starting a top-secret project consisting of $s$ subprojects. There are $b$ branches (with $b \geq s$) that must be partitioned into $s$ disjoint groups, where each group is responsible for one subproject.

At the end of each month, each branch sends a different message to every other branch in its group. To comply with ICPC’s secure communication protocol, when branch $i$ wants to send a message to branch $j$, it first encrypts the message with its secret key and sends it to the headquarters via a courier. The headquarters decrypts the message and then re-encrypts it using branch $j$'s secret key. A courier, who can carry only one message at a time, then delivers the message to branch $j$. Consequently, the distance a courier travels for a message from branch $i$ to branch $j$ is the sum of the shortest path from node $i$ to the headquarters and from the headquarters to node $j$, i.e. $d(i,H)+d(H,j)$.

For a group $G$ with $|G|$ branches whose distances from the headquarters are $d_1, d_2, \dots, d_{|G|}$, all branches send messages to each other. Hence the total courier distance incurred by group $G$ is

Your task is to assign the $b$ branches, located in a road network, to $s$ subprojects (each group non-empty) so that the overall total distance travelled by the couriers (i.e. the sum of the costs over all groups) is minimized. In order to determine this distance, you are given the road network, the location of the headquarters, the locations of the branches, and the roads with associated distances. Note that the network is undirected and the distance between any two nodes is defined as the length of the shortest path between them.

inputFormat

The input is given as follows:

1. The first line contains two integers $n$ and $m$, representing the number of nodes and edges in the road network.
2. The second line contains an integer $H$, the index of the node where the ICPC headquarters is located.
3. The third line contains two integers $b$ and $s$, where $b$ is the number of branches and $s$ is the number of subprojects ($1 \le s \le b$).
4. The fourth line contains $b$ integers, each denoting the node where a branch is located.
5. The following $m$ lines each contain three integers $u$, $v$, and $w$, indicating that there is an undirected road between nodes $u$ and $v$ with distance $w$.

outputFormat

Output a single integer, the minimum total distance that all couriers need to travel to deliver all messages after optimally partitioning the branches into $s$ groups.

sample

4 4
1
3 1
1 2 3
1 2 2
2 3 3
3 4 4
1 4 10

28