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가 되는 데 걸린 시간의 최솟값을 출력한다.