Problem Statement

The Republic of Shiomusubi has $N$ towns, town $1$ through town $N$, and $M$ roads, road $1$ through road $M$. Road $i$ bidirectionally connects $A_i$ and $B_i$ ($A_i < B_i$) and has length $C_i$.

In the Republic of Shiomusubi, between arriving at town $i$ and departing from town $i$, you must eat shiomusubi (salted rice balls) for exactly $T_i$ minutes. (You must also eat shiomusubi when departing from town $1$, but you do not need to eat when you arrive at town $N$.)

You may pass through the same town multiple times, and you must eat shiomusubi each time.

Also, if you have eaten shiomusubi for a total of $P$ minutes since departing from town $1$, you can traverse a road of length $l$ in $\lfloor \frac{l}{P} \rfloor$ minutes. (It can be proved that, under the constraints, you never traverse a road with $P=0$.)

Liunxmetel wants to go on an outing from town $1$, where he lives, to town $N$, where New Puroland is located. Find the minimum time it takes Linuxmetel to reach town $N$.

Note that Linuxmetel cannot move to another town except via roads. Also, he never eats shiomusubi anywhere other than in a town.

Input

$N\ M$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
　　$\vdots$
$A_M\ B_M\ C_M$
$T_1\ T_2\ \ldots\ T_N$

• All input values are integers.
• $2 \leq N\leq 100$
• $1 \leq M\leq\min\left(\frac{N(N-1)}{2},100\right)$
• $1 \leq A_i < B_i \leq N$
• If $i \neq j$, then $(A_i, B_i) \neq (A_j, B_j)$
• $1 \leq C_i \leq 1000$
• $0 \leq T_i \leq 100$
• $T_1 \neq 0,T_N = 0$
• The given input data guarantees that it is possible to travel from town $1$ to town $N$ by passing through $0$ or more towns.

Output

Print the minimum time it takes Linuxmetel to reach town $N$ as a positive integer.

Also, print a newline at the end.

Sample

2 1
1 2 10
1 0

11

4 4
1 2 9
1 3 6
2 4 8
3 4 5
3 1 2 0

8

6 15
2 6 202
1 2 185
3 6 978
2 3 976
3 4 445
1 6 795
1 5 951
2 4 626
4 5 265
1 4 501
1 3 685
2 5 899
5 6 766
3 5 923
4 6 343
46 19 23 75 48 0

63