Caprica is one of the 12 colonial planets, but it was completely destroyed by the cylons, robots made by humans that had rebelled. Before the attack, Doctor Gaius Baltar had the following problem. Caprica has N cities, numbered from 0 to N − 1, and M bidirectional roads connecting them, in a way that exists a path between every pair of cities. Let X and Y be two disjoint and non-empty subsets of this N cities. The problem is to find the smallest path length between any cities x and y where x ∈ X and y ∈ Y. A path length is the sum of the distance of each road in this path.

Input

Each test case is described using several lines. The first line contains four integers N, M, A and B representing respectively the number of cities (2 ≤ N ≤ 1000), the number of roads (1 ≤ M ≤ 10⁴), the number of cities in X (2 ≤ A ≤ 1000), and the number of cities in Y (2 ≤ B ≤ 1000), where A + B ≤ N.

The second line contains A integers and the third line contains B integers, representing the cities in X and Y respectively. Each of the next M lines describes a road using three integers, u, v, and d, indicating that there is a road between the cities u and v with distance d (1 ≤ d ≤ 10⁴). The last test case is followed by a line containing four zeros.

Output

For each test case output, in a single line, the integer representing the smallest path length between x and y where x ∈ X and y ∈ Y .

Example

Input:
4 4 2 2
0 1
2 3
0 1 10
0 2 20
1 3 10
2 3 10
0 0 0 0

Output:
10