집 구하기

안양에 사는 상혁이는 4년 동안 통학하느라 지쳐서 서울에 집을 구하려고 한다. 상혁이가 원하는 집은 다음 세 조건을 모두 만족한다.

• 맥세권: 집에서 가장 가까운 맥도날드까지의 최단거리가 $x$ 이하이다.
• 스세권: 집에서 가장 가까운 스타벅스까지의 최단거리가 $y$ 이하이다.
• 앞의 두 조건을 함께 만족하는 집 가운데 두 최단거리의 합이 가장 작다.

통학 때문에 스트레스를 많이 받은 상혁이는 집을 고르기 어려워한다. 상혁이 대신 이 문제를 풀어 주자. 이사 갈 지역의 지도가 가중치 그래프로 주어지고 맥도날드와 스타벅스의 위치가 정점 번호로 주어질 때, 상혁이가 원하는 집의 두 최단거리 합을 출력하는 프로그램을 작성하시오. 맥도날드도 스타벅스도 없는 정점에는 모두 집이 있다.

위 지도에서 사각형은 맥도날드가, 별은 스타벅스가 있는 정점이고 각 원은 집이 있는 정점이다. $x$가 6이고 $y$가 4이면 답이 되는 집은 정점 6이다. 맥도날드까지의 최단거리가 2, 스타벅스까지의 최단거리가 4라서 합이 6이기 때문이다. 정점 7도 맥세권이면서 스세권이지만 두 최단거리가 각각 6과 2여서 합이 8이고, 정점 6의 값보다 크므로 답이 아니다. 정점 2, 3, 4는 두 조건을 함께 만족하지 못하므로 답이 될 수 없다.

첫 줄에 정점의 개수 $V(3 \le V \le 10000)$와 도로의 개수 $E(0 \le E \le 300000)$가 주어진다. 다음 $E$개의 줄에 각 도로를 나타내는 세 정수 $u$, $v$, $w$가 순서대로 주어진다. 이는 정점 $u$와 $v(1 \le u, v \le V)$ 사이에 가중치가 $w(1 \le w < 10000)$인 도로가 있다는 뜻이다. $u$와 $v$는 서로 다르며, 같은 두 정점 사이에 도로가 여러 개 있을 수도 있다.

그다음 줄에 맥도날드의 개수 $M(1 \le M \le V-2)$과 맥세권 조건 $x(1 \le x \le 100000000)$가 주어지고, 그다음 줄에 맥도날드가 있는 정점 번호 $M$개가 주어진다. 이어지는 줄에 스타벅스의 개수 $S(1 \le S \le V-2)$와 스세권 조건 $y(1 \le y \le 100000000)$가 주어지고, 그다음 줄에 스타벅스가 있는 정점 번호 $S$개가 주어진다.

• 맥도날드나 스타벅스가 있는 정점에는 집이 없다.
• 한 정점에 맥도날드와 스타벅스가 함께 있을 수 있다.
• 집이 있는 정점이 하나 이상 있다.

상혁이가 원하는 집에서 맥도날드까지의 최단거리와 스타벅스까지의 최단거리의 합을 출력한다. 조건을 만족하는 집이 없으면 -1을 출력한다.