問題文

ゆーてぃーさんは, 電車に乗ってお出かけすることにしました.

この都市には $N$ 個の駅と $M$ 本の路線があります. 駅には $1$ から $N$ までの番号が付いています. $i$ 番目の路線は異なる駅 $U_i$ と駅 $V_i$ を双方向に結んでいて, 移動するには $W_i$ だけの時間がかかります. 同じ駅の組 $(U_i, V_i)$ に対して複数の路線が存在することがあります.

各駅には発車時刻が決まっており, $j$ 番目の駅から発車する電車は時刻が $A_j$ の倍数の時に発車します. 電車の到着時刻などに依存しません. 発車時刻に時刻 $0$ は含まれません.

例えば, 時刻 $4$ の時に駅 $1$ にいて, 駅 $2$ に向かうとします. 駅 $1$ から駅 $2$ には $4$ だけの時間がかかり, 駅 $1$ の発車時刻が $A_j=3$ の倍数の場合, 時刻 $6$ に駅 $1$ を出発し, 時刻 $10$ に駅 $2$ に到着します.

なお, 駅に到着する時刻と同じ時刻にその駅を発車する電車にも乗ることができます.

また, 駅 $i$ から時刻 $A_i \times k$ $(k \geq 1)$ に発車するすべての電車について, $k$ が $B_i$ の倍数である場合, 通常の移動時間に加えて $C_i$ だけ余分に時間が生じます.

ゆーてぃーさんは時刻 $0$ に駅 $1$ にいます. 駅 $N$ への到着時刻の最小値を求めてください.

入力は, 駅 $1$ から駅 $N$ に必ず到達できるように与えられます. 制約から答えは $2^{64}$ 以下であることが証明できます.

制約

• 入力は全て整数
• $2 \leq N \leq 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq U_i, V_i \leq N$
• $U_i \neq V_i$
• $1 \leq W_i \leq 10^9$
• $1 \leq A_j \leq 10^9$
• $2 \leq B_i \leq 100$
• $1 \leq C_i \leq 10^9$
• 同じ駅の組 $(U_i, V_i)$ が複数回与えられることがある
• 駅 $1$ から駅 $N$ に必ず到達できる

入力

$N$ $M$
$U_1$ $V_1$ $W_1$
$U_2$ $V_2$ $W_2$
$\vdots$
$U_M$ $V_M$ $W_M$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$
$C_1$ $C_2$ $\cdots$ $C_N$

出力

駅 $N$ への到着時刻の最小値を出力してください.

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

サンプル

4 4
1 2 4
1 3 3
2 4 2
3 4 3
2 3 4 5
3 2 3 2
1 1 1 1

9

6 5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
3 1 4 1 5 9
2 3 4 5 6 7
7 6 5 4 3 2

11

5 9
1 2 80
1 3 30
1 4 60
2 3 10
2 4 10
2 5 90
3 4 120
3 5 50
4 5 70
5 6 7 8 9
3 3 3 3 3
10 20 30 40 50

85