Problem D
Doomsday

Public domain, Munds Mountain Trail by Coconino NF Photography via Flickr

Input

The first line contains four integers $n$, $m$, $w$, $f$, where $1 \leq n \leq 50\, 000$ is the number of hidden locations, $0 \leq m \leq 150\, 000$ is the number of trails in the network, $1 \leq w \leq n$ is the number of water depots in total, and $1 \leq f \leq n$ is the number of food depots in total. Your base is at location $0$. The second line contains $w$ space-separated integers $u_1, u_2, \ldots , u_ w$, which represents the (distinct) locations of the water depots ($0 \leq u_ i < n$ for each $i$). The third line contains $f$ space-separated integers $v_1, v_2, \ldots , v_ f$, which represents the (distinct) locations of the food depots ($0 \leq v_ i < n$ for each $i$).

The next $m$ lines each describe a (bidirectional) trail in the network. The $i^{\text {th}}$ such line contains three space-separated integers $a_ i$, $b_ i$ and $t_ i$ indicating that there is a trail between location $a_ i$ and $b_ i$ which takes $t_ i$ hours to traverse ($0 \leq a_ i, b_ i < n$ and $0 \leq t_ i < 100$ for each $i$).

Output

Output a single integer, the minimum number of hours required to fetch both food and water and bring it back to base.

7 7 2 2
3 6
4 5
0 1 3
0 2 1
1 3 3
1 4 1
2 5 2
2 6 10
4 5 1

14