33906번 - 점심 나가서 먹기

문제

매일같이 알고리즘 대회 준비와 학교 수업으로 바쁜 준호는 하루 종일 머리를 혹사당하고 있다.

가혹한 일정에 정신이 나가버린 준호는... 점심을 나가서 먹기로 했다!

준호는 $N$개의 건물들과 $M$개의 도로들로 이루어진 도시에 살고 있다. 도시의 건물들은 1ドル$번부터 $N$번까지 번호가 붙어 있으며, 도시 곳곳에는 공사 중인 도로도 있어 어떤 건물들은 방문할 수 없는 경우도 있다. 도시에는 수많은 식당과 카페들이 있지만, 가난한 준호는 방문할 수 있는 곳 중 가장 싼 식당과 가장 싼 카페를 찾아 점심을 해결하고 돌아오기로 했다. (물론 가장 싼 식당과 카페가 같은 건물에 있을 수도 있다.)

점심을 빠르게 먹고 돌아오고 싶은 준호는 식당과 카페를 들르는 순서는 상관없이, 최소 거리로 돌아오고 싶어 한다.

준호가 집(1ドル$번 건물)에서 출발하여 도달할 수 있는 가장 싼 식당과 카페를 들른 후, 다시 집으로 돌아오는 최소 거리를 구해보자.

입력

첫 번째 줄에 준호의 집을 포함한 건물의 수 $N(2 ≤ N ≤ 100,000円)$과 건물 간의 도로 개수 $M(1 ≤ M ≤ 200,000円)$이 주어진다.

두 번째 줄에 $i$번 건물 식당들 중 최소 가격 $x_i(0 ≤ x_i ≤ 10^9)$가 $N$개의 정수로 주어진다. 각각의 가격은 모두 다르며, 0ドル$일 경우 해당 건물에는 식당이 없다.

세 번째 줄에 $j$번 건물 카페들 중 최소 가격 $y_j(0 ≤ y_j ≤ 10^9)$가 $N$개의 정수로 주어진다. 각각의 가격은 모두 다르며, 0ドル$일 경우 해당 건물에는 카페가 없다.

다음 $M$개의 줄에는 세 개의 정수 $u, v, w(1 ≤ u, v ≤ N; 1 ≤ w ≤ 10,000円)$가 주어지며, 이는 $u$번 건물과 $v$번 건물이 거리 $w$인 양방향 도로로 연결되어 있음을 의미한다.

$u$와 $v$는 같을 수 있다.

준호의 집에는 식당과 카페가 없으며, 준호의 집에서 적어도 하나의 식당과 카페에 도달할 수 있음이 보장된다.

출력

집(1번 건물)에서 출발하여 도달할 수 있는 가장 싼 식당과 카페를 들렀다가 다시 집으로 돌아오는 최소 거리를 출력한다.

제한

힌트