Problem Statement

The binap galaxy consists of $N$ planets, planet $1$ through planet $N$. You are currently on planet $1$ and have $1$ warp ticket. Find the minimum time required to reach planet $N$.

There are the following $2$ ways to travel between planets in the binap galaxy.

・Travel along a route

There are $M$ designated routes. Route $i$ connects planet $U_i$ and planet $V_i$ bidirectionally, and can be traveled in either direction in time $T_i$.

・Travel by warp navigation

Each planet has a value called its distortion degree. The distortion degree of planet $i$ ( $1 \leq i \leq N$ ) is $W_i$. When you are on any planet $i$, you can consume $1$ warp ticket to move to any planet $j$ in time $W_iW_j$, the product of their distortion degrees.

Input

$N$ $M$
$W_1$ $W_2$ $\ldots$ $W_N$
$U_1$ $V_1$ $T_1$
$U_2$ $V_2$ $T_2$
$\vdots$
$U_M$ $V_M$ $T_M$

• $2 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq W_i \leq 10^9$ ( $1 \leq i \leq N$ )
• $1 \leq U_i < V_i \leq N$ ( $1 \leq i \leq M$ )
• $(U_i, V_i) = (U_j, V_j) \iff i = j$
• $1 \leq T_i \leq 10^{12}$ ( $1 \leq i \leq M$ )
• All input values are integers.

Output

Output the answer as an integer.

Print a newline at the end.

Sample

3 2
4 2 2
1 2 3
1 3 9

7

3 3
314 159 265
1 2 1
2 3 2
1 3 4

3

13 15
67 66 182 81 97 121 200 94 199 25 99 12 171
8 13 172
4 13 579
6 9 53
1 3 369
1 8 1367
2 6 1202
5 8 145
2 8 77
11 12 361
5 7 70
10 13 104
11 13 1411
1 11 115
6 11 63
4 10 222

880