Super Bus

Bo-seon, who is visiting Jinju, boards a bus to reach the Jinyangho Observatory, which she reserved in advance. She arrives at a nearby bus stop, but the bus information display shows no arrivals at all. Confused, she checks around until a message arrives from Jun-hee, a college classmate.

How does it taste?

Jun-hee sent it. In college, Jun-hee was a risotto fan who had to eat gukbap every day because of Bo-seon, a gukbap fanatic, and has held a grudge ever since. When Jun-hee learned that Bo-seon was visiting Jinju, Jun-hee used hacking skills to break into the bus information system and stop city buses from running.

Jinju treated the hacked bus system as a disaster and started running Super Bus. To keep Super Bus running smoothly, all other means of transportation were banned.

Jinju has $N$ bus stops numbered from 1 in order. There are $M$ bidirectional roads, each joining two different bus stops, with a fixed travel time on Super Bus. Two bus stops may be joined by two or more roads. Each bus stop has a disaster code, a positive integer at most $5\,000\,000$. Super Bus only runs on a road between two bus stops when the sum of their disaster codes is a prime. Here, a prime is an integer of at least 2 whose only divisors are 1 and itself.

Bo-seon starts at stop 1, and the Jinyangho Observatory is at stop $N$. The stops are far apart, so Super Bus is the only way to travel. Bo-seon can board any Super Bus as soon as she arrives at a stop, and boarding or alighting takes no time. Find the shortest time for Bo-seon to reach stop $N$.

The first line contains the number of bus stops $N$ and the number of bidirectional roads $M$, separated by a space. ($2 \le N \le 400\,000$; $1 \le M \le 1\,000\,000$)

The second line contains the disaster codes $D_1, \dots, D_N$ of the bus stops, separated by spaces. ($1 \le D_i \le 5\,000\,000$)

From the third line onward, the next $M$ lines each contain $u_i$, $v_i$, and $w_i$, separated by spaces. This describes the $i$-th bidirectional road, which joins stop $u_i$ and stop $v_i$ and takes $w_i$ time to travel on Super Bus. ($1 \le u_i < v_i \le N$; $1 \le w_i \le 400\,000$)

All input numbers are integers.

On the first line, print the shortest time to reach the Jinyangho Observatory. If it cannot be reached, print Now where are you?.

Python 3 users are advised to submit with PyPy3.