Super Bus

진주 나들이를 온 보선이는 미리 예약해 둔 진양호 전망대에 가려고 버스를 타기 위해 가까운 버스 정류장에 도착했다. 그런데 버스정보안내단말기에 도착 정보가 한 대도 표시되지 않았다. 당황한 보선이에게 대학 동기 준희에게서 문자가 왔다.

맛이 어때?

준희의 짓이었다. 대학 시절 국밥 마니아 보선이 때문에 매일 국밥만 먹어야 했던 리조또 마니아 준희는 그때부터 앙심을 품고 있었다. 보선이가 진주에 놀러 왔다는 것을 알게 된 준희는 해킹 실력을 발휘해 버스정보시스템을 뚫었고, 그 결과 시내버스가 다니지 못하게 되었다.

진주시는 버스정보시스템이 해킹된 지금 상황을 사실상 재난으로 보고 Super Bus 운행을 시작했다. Super Bus가 원활하게 운행되도록 다른 교통수단은 모두 이용할 수 없게 했다.

진주에는 버스 정류장이 $N$개 있고 1번부터 차례로 번호가 붙어 있다. 서로 다른 두 버스 정류장을 잇는 양방향 도로가 $M$개 있으며, 각 도로는 Super Bus로 지나가는 데 걸리는 시간이 정해져 있다. 임의의 두 버스 정류장 사이에 도로가 두 개 이상 있을 수 있다. 각 버스 정류장에는 $5\,000\,000$ 이하의 양의 정수인 재난 코드가 부여되어 있다. Super Bus는 두 버스 정류장의 재난 코드 합이 소수인 도로에서만 운행한다. 여기서 소수는 1과 자기 자신 외에 약수가 없는 2 이상의 정수를 뜻한다.

보선이는 1번 정류장에서 출발하고, 진양호 전망대는 $N$번 정류장에 있다. 정류장끼리는 서로 멀리 떨어져 있어 Super Bus로만 이동할 수 있다. 정류장에 도착하면 원하는 Super Bus를 바로 탈 수 있고, 승하차에 걸리는 시간은 없다고 가정한다. 이 조건에서 보선이가 $N$번 정류장에 가장 빨리 도착할 때까지 걸리는 시간을 구하라.

첫 번째 줄에 버스 정류장의 개수 $N$과 양방향 도로의 개수 $M$이 공백으로 구분되어 주어진다. ($2 \le N \le 400\,000$; $1 \le M \le 1\,000\,000$)

두 번째 줄에 각 버스 정류장의 재난 코드 $D_1, \dots, D_N$이 공백으로 구분되어 주어진다. ($1 \le D_i \le 5\,000\,000$)

세 번째 줄부터 $M$개의 줄에 걸쳐 도로 정보 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어진다. 이는 $u_i$번 정류장과 $v_i$번 정류장을 잇고, Super Bus로 지나가는 데 $w_i$의 시간이 걸리는 $i$번째 양방향 도로를 뜻한다. ($1 \le u_i < v_i \le N$; $1 \le w_i \le 400\,000$)

입력으로 주어지는 모든 수는 정수이다.

첫 번째 줄에 진양호 전망대에 가장 빨리 도착할 때까지 걸리는 시간을 출력한다. 도착할 수 없다면 Now where are you?를 출력한다.

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.