Minimum Obstruction Cost in Recovery Route Tree

In a campus there are N areas connected by M bidirectional roads. Two bike‐sharing companies, A and B, operate on campus. B’s recovery action starts from its headquarters located at area K. For each area X, B uses a unique recovery route from K to X which is chosen by the following rule: among all shortest paths from K to X, the one whose immediate predecessor of X has the smallest numerical label is selected. This collection of recovery routes forms a tree rooted at K (called the recovery route tree).

B company designates some areas as recovery areas and, separately, some areas as deposit areas. In the recovery route tree, all nodes on the paths from K to each recovery area are "marked" (note that these include K, the recovery areas, and the lowest common ancestors of every pair of recovery areas). For every marked deposit area X (with X (\neq K)), B’s recovery route from K to X must contain at least one segment – that is, a contiguous set of roads connecting two marked nodes – whose every road is obstructed by company A. Obstructing a road costs an amount equal to its length.

Your task is to help company A choose a set of roads to obstruct (with minimum total cost) so that, for every marked deposit area X (other than K), there exists at least one pair of marked nodes on the path from K to X with all roads between them obstructed.

The key observation is that the marked nodes in the recovery route tree are exactly the nodes on the unique paths from K to all recovery areas. Hence, if we contract the recovery route tree to the "marked subtree" (which is the minimal subtree connecting K and all recovery areas), the problem reduces to a minimum cut on a tree: choose some edges (each with cost equal to the sum of original road lengths on the corresponding segment) so that every marked deposit node (other than K) is separated from K by at least one obstructed edge. This can be solved by a dynamic programming on the marked subtree.

The recovery route tree is constructed as follows: [ \text{For each node } X \neq K,; \text{choose as its parent the node } Y \text{ for which } Y \text{ lies on a shortest path from } K \text{ to } X \text{ and has the smallest label among all candidates.} ]

Let R be the set of recovery areas and D the set of deposit areas. Define the marked set as the union of all nodes on the paths from K to each node in R. Then, for every node X in D(\cap)marked with X (\neq K), the unique path from K to X in the marked subtree must contain at least one edge that is chosen (i.e. obstructed). The goal is to choose a set of edges with minimum total cost so that this condition is satisfied for every such X.

Below is the input/output format and several solution codes in Python3, C++, Java, C, and JavaScript.

inputFormat

The input begins with a line containing three integers N, M and K (1 (\le) K (\le) N). Each of the next M lines contains three integers u, v, w (1 (\le) u, v (\le) N, w > 0) meaning there is a bidirectional road connecting areas u and v with length w. It is guaranteed that the campus is connected.

The next line starts with an integer r followed by r distinct integers representing the recovery areas.

The following line starts with an integer d followed by d distinct integers representing the deposit areas.

Note: In the recovery route tree (constructed from the unique recovery route from K to every area as defined above), the marked set is defined as all nodes on the paths from K to each recovery area. Only marked deposit areas (i.e. those deposit areas that lie in the marked set and are not K) need to have at least one completely obstructed segment on their unique path from K.

outputFormat

Output a single integer – the minimum total cost required to obstruct B company's recovery operation.

sample

6 5 1
1 4 3
1 5 9
5 6 7
1 2 5
2 3 2
3 4 5 6
2 4 6

10