問題文

binap銀河は惑星 $1$ から惑星 $N$ の $N$ 個の惑星で構成されます。今あなたは惑星 $1$ にいて $1$ 枚のワープチケットを持っています。惑星 $N$ にたどり着くのにかかる時間の最小値を求めてください。

binap銀河で惑星間を移動する方法は以下の $2$ 通りです。

・航路に沿った移動

$M$ 本の航路が規定されています。航路 $i$ は惑星 $U_i$と惑星 $V_i$ を双方向に繋いでおり時間 $T_i$ で行き来できます。

・ワープ航法による移動

各惑星は歪み度という値をもちます。惑星 $i$ ( $1 \leq i \leq N$ ) の歪み度は $W_i$です。任意の惑星 $i$ にいるとき、ワープチケットを $1$ 枚消費することで任意の惑星 $j$ へ歪み度の積 $W_iW_j$ の時間で移動できます。

入力

$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$ )
• 入力はすべて整数

出力

答えを整数で出力してください。

最後に改行してください。

サンプル

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