Greg Brandon Sr. is working at a shipping company in Redmond that specializes in shipping Chromium. Redmond contains $n$ intersections and $m$ two-way roads that directly connect two intersections (Redmond can be modelled as a graph with $n$ vertices and $m$ edges). It is always possible to travel from any intersection to any other intersection via the roads.

The shipping company has two warehouses and $s$ employees. The warehouses and employees are currently located at some of the intersections in Redmond. Greg needs to make $t$ deliveries to his clients who are also located at some of the intersections in Redmond. For each delivery, one of his employees will travel to either warehouse to pick up the item to deliver, then travel to the corresponding client. Each warehouse always contains an infinite amount of each item. Greg would like to minimize the total distance travelled by his employees (he does not care about the return trip). Each employee may make at most one delivery.

-----Input-----
The first line of input contains four space-separated integers $n$, $m$, $s$, and $t$ ($2\le n\le 10^5$, $n-1\le m\le 2\cdot 10^5$, and $1\le t\le s\le 10^5$), denoting the number of intersections, the number of roads, the number of employees, and the number of deliveries respectively.

The second line of input contains two space-separated integers $a$ and $b$ ($1\le a, b\le n$), denoting the locations of the two warehouses. The warehouses could be at the same intersection.

The third line of input contains $s$ space-separated integers $x_ i$ ($1\le x_ i\le n$), denoting the locations of the $s$ employees. The $x_ i$’s are not necessarily distinct.

The fourth line of input contains $t$ space-separated integers $y_ i$ ($1\le y_ i\le n$), denoting the locations of the clients for the $t$ deliveries. The $y_ i$’s are not necessarily distinct.

Each of the next $m$ lines of input contains three space-separated integers $u$, $v$, and $d$ ($1\le u, v\le n$, $u\neq v$, and $1\le d\le 10^8$), denoting a road of distance $d$ connecting intersections $u$ and $v$. It is always possible to travel from one intersection to all other intersections.

-----Output-----
The only line of output should contain a single integer denoting the minimum total distance.

-----Examples-----
Sample Input 1:
7 8 3 2
1 2
7 3 4
5 6
1 3 2
1 4 1
1 5 1
1 6 6
2 3 9
2 4 2
2 6 4
7 6 5
Sample Output 1:
9

Sample Input 2:
2 1 1 1
2 2
1
1
1 2 1
Sample Output 2:
2

Source: kattis | Difficulty: HARD


Solutions: