Woburn Challenge 2016-17 Round 3 - Senior Division

In the world of Pokémon Navy Green, there are $N$ $(2\le N\le 200000)$ towns, with $M$ $(0\le M\le 200000)$ routes running amongst them. At the beginning of the game, you find yourself in town $1$ with a starting Pokémon of your choice – a cute level $1$ Pyglion! Your objective is to reach town $N$ by following a sequence of routes.

The $i$-th route connects distinct towns $A_i$ and $B_i$ $(1\le A_i,B_i\le N)$, and can be walked along in either direction. No pair of towns are directly connected by multiple routes. However, the routes are also crawling with dangerous Pokémon. As such, you can only dare venture along the $i$-th route if your Pyglion's level is currently no smaller than $C_i$ $(1\le C_i\le {10}^9)$.

As mentioned, your Pyglion's level is initially $1$, but it can be increased through intensive training. Each town has its own training gym for that purpose. However, some gyms are more efficient than others – in particular, in the $i$-th town, it takes $T_i$ $(1\le T_i\le {10}^9)$ minutes of training to increase your Pyglion's level by $1$. This $T_i$–minute process can be repeated as many times as you'd like.

You'd hate to tucker out your poor Pyglion more than necessary, so you'd like to reach town $N$ after spending as little total time training in gyms as possible. Note that time spent walking along routes isn't relevant, and that you may revisit towns on your adventure as often as you'd like. Please determine the minimum number of minutes of training required to reach town $N$, or determine that you can't complete your trip no matter how much training you put your Pyglion through.

In test cases worth $13/18$ of the points, $N\le 500$, $M\le 500$, and $C_i\le 500$.

Input Specification

The first line of input consists of two space-separated integers $N$ and $M$.
$N$ lines follow, with the $i$-th of these lines consisting of a single integer, $T_i$ (for $i=1\dots N$).
$M$ lines follow, with the $i$-th of these lines consisting of three space-separated integers $A_i$, $B_i$, and $C_i$, (for $i=1\dots M$).

Output Specification

Output one line consisting of a single integer – the minimum number of minutes of training required to reach town $N$, or -1 if it can't be done.
Note that the answer may not necessarily fit within a $32$-bit signed integer (you may need the long long type in C++, or long in Java).

Sample Input

6 8
14
5
8
10
2
4
1 4 5
1 2 8
4 5 12
3 1 2
6 3 11
2 3 14
5 6 4
2 4 6

Sample Output

71

Sample Explanation

One optimal sequence of actions is as follows:

• Train in town $1$ for $14$ minutes (up to level $2$).
• Walk to town $3$.
• Train in town $3$ for $32$ minutes (up to level $6$).
• Walk to town $1$.
• Walk to town $4$.
• Walk to town $2$.
• Train in town $2$ for $25$ minutes (up to level $11$).
• Walk to town $1$.
• Walk to town $3$.
• Walk to town $6$.