### Woburn Challenge 2016-17 Round 3 - Senior Division

## Problem 2: Training Regimen

In the world of Pokémon Navy Green, there are `N` (2 ≤ `N` ≤ 200,000) towns, with `M` (0 ≤ `M` ≤ 200,000) 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`(1 ≤

_{i}`A`,

_{i}`B`≤

_{i}`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`(1 ≤

_{i}`C`≤ 10

_{i}^{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 ≤

`T`≤ 10

_{i}^{9}) minutes of training to increase your Pyglion's level by 1. This

`T`–minute process can be repeated as many times as you'd like.

_{i}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` ≤ 500, `M` ≤ 500, and `C _{i}` ≤ 500.

### Input Format

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

`N`).

`M`lines follow, with the

`i`-th of these lines consisting of three space-separated integers

`A`,

_{i}`B`, and

_{i}`C`, (for

_{i}`i`= 1..

`M`).

### Output Format

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 2.
- Train in town 2 for 25 minutes (up to level 11).
- Walk to town 1.
- Walk to town 3.
- Walk to town 6.

All Submissions

Best Solutions

**Point Value:** 12 (partial)

**Time Limit:** 3.00s

**Memory Limit:** 64M

**Added:** Feb 19, 2017

**Author:** SourSpinach

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...