Problem Statement

Yu-T decided to go out by train.

This city has $N$ stations and $M$ railway lines. The stations are numbered from $1$ to $N$. The $i$-th line bidirectionally connects distinct stations $U_i$ and $V_i$, and traveling along it takes $W_i$ units of time. There may be multiple lines for the same pair of stations $(U_i, V_i)$.

Each station has fixed departure times: trains departing from the $j$-th station depart at times that are multiples of $A_j$. This does not depend on the arrival times of trains or the like. Time $0$ is not included in the departure times.

For example, suppose you are at station $1$ at time $4$ and are heading to station $2$. If traveling from station $1$ to station $2$ takes $4$ units of time, and the departure times of station $1$ are the multiples of $A_j=3$, then you depart from station $1$ at time $6$ and arrive at station $2$ at time $10$.

Note that you can also board a train that departs from a station at the same time as you arrive at that station.

In addition, for every train departing from station $i$ at time $A_i \times k$ $(k \geq 1)$, if $k$ is a multiple of $B_i$, an extra $C_i$ units of time are required on top of the normal travel time.

Yu-T is at station $1$ at time $0$. Find the minimum possible arrival time at station $N$.

The input guarantees that station $N$ is always reachable from station $1$. It can be proved from the constraints that the answer is at most $2^{64}$.

Constraints

• All inputs are integers.
• $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$
• The same pair of stations $(U_i, V_i)$ may be given multiple times.
• Station $N$ is always reachable from station $1$.

Input

$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$

Output

Output the minimum possible arrival time at station $N$.

Print a newline at the end.

Sample

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