31008번 - Road To The LegenD,

문제

토니는 LegenD가 되기 위한 여정에 나섰다. 기나긴 여정 중에는 1ドル$부터 $N$까지 번호가 붙은 $N$개의 마을을 거칠 수 있고, $u$번 마을에는 마을의 격 $h_u$가 있다. 토니는 처음에 1ドル$번 마을에 있다. 신이 정한 특정한 마을에 도달하면 토니는 LegenD가 될 수 있다.

마을 사이를 잇는 길은 두 종류로 편한 길과 고행의 길이 있다.

편한 길은 고대부터 존재하던 길로 총 $M$개가 있으며 $i$번째 편한 길을 통하면 $u_i$번 마을에서 $v_i$번 마을로 시간 $t_i$를 들여 이동할 수 있다. 같은 마을 번호 쌍 $(u_i, v_i)$에 대해 $u_i$번 마을에서 $v_i$번 마을로 이동 가능한 편한 길이 둘 이상 존재할 수 있다.

고행의 길은 선대 LegenD에 의해 0ドル$개 이상 설치되었다. $u$번 마을과 $u$번 마을로부터 편한 길 정확히 하나를 지나 도착할 수 있는 마을들 중 가장 격이 높은 마을의 격을 $H_u$라고 하자. 1ドル$ 이상 $N$ 이하의 정수 $u, v$에 대해 $H_u \lt h_v$라면 $u$번 마을에서 $v$번 마을로 가는 고행의 길이 설치되어 있다. $u$번 마을에서 출발하는 고행의 길 하나를 통해 $v$번 마을로 가는 데에는 시간 $p_u$가 걸린다.

신은 도착하면 LegenD가 되는 마을을 정할 때, 토니가 도달할 수 있는 마을 중 해당 마을에 도달하기까지 걸리는 최소시간이 가장 긴 마을을 정했다. 토니가 LegenD가 되는 데 성공했다면, 걸린 시간은 최소 얼마일까?

입력

첫째 줄에 마을의 수 $N$과 편한 길의 수 $M$가 공백으로 구분되어 주어진다. $(2 \le N \le 200,000円$; 1ドル \le M \le 400,000円)$

둘째 줄에 각 마을의 격을 나타내는 정수 $h_1, h_2, \cdots, h_N$이 공백으로 구분되어 주어진다. $(1 \le h_u \le 10^9)$

셋째 줄에 각 마을에서 출발하는 고행의 길을 지날 때 걸리는 시간을 나타내는 정수 $p_1, p_2, \cdots, p_N$이 공백으로 구분되어 주어진다. $(1 \le p_u \le 10^9)$

다음 $M$개 줄 중 $i$번째 줄에, $i$번째 편한 길의 출발 마을 $u_i$와 도착 마을 $v_i,ドル 이동 시간을 나타내는 정수 $t_i$가 공백으로 구분되어 주어진다. $(1 \le u_i, v_i \le N;$ 1ドル \le t_i \le 10^9;$ $u_i \ne v_i)$

출발 마을과 도착 마을이 같은 편한 길이 둘 이상 존재할 수 있다.

출력

첫째 줄에 토니가 LegenD가 되는 데 걸린 시간의 최솟값을 출력한다.

제한

힌트