24240번 - Doomsday 다국어

Doomsday is near! Or at least that’s what your brother is telling you. In his preparations he has constructed a clever network of well concealed food depots and water depots far out in a mountainous region. You are in your base, and the alarm goes off: how quickly can you fetch both food and water supplies?

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 a single integer, the minimum number of hours required to fetch both food and water and bring it back to base.