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.

제한

힌트