Fastest Route with Quarantine (Directed Graph)

Country A has N cities numbered from 1 to N. Xiaoming, an employee in city 1, has been ordered to travel to city N. Due to the pandemic, many direct transportation options (like flights) are closed and he has to travel by road through intermediate cities. There are M available directed routes between cities; each route goes from city u to city v and takes w time. Furthermore, due to epidemic prevention measures, upon arriving at any city (except city 1) Xiaoming must undergo a quarantine period before he can depart from that city. In other words, when leaving city u (with u ≠ 1) via any outgoing route, an additional waiting time t_u is incurred. Note that no quarantine is needed at the start (city 1) and once city N is reached the journey is over (no quarantine needed). Your task is to plan a route from city 1 to city N that minimizes the total time (including travel and quarantine times).


Important: The routes are directed. That is, if a route is given from u to v, it can only be used in that direction.

inputFormat

The first line contains two integers N and M. The second line contains N integers t₁, t₂, ..., tₙ, where tᵢ denotes the quarantine time at city i. (Note: although quarantine information is given for all cities, city 1 does not require quarantine as Xiaoming can leave immediately, and when arriving at city N, quarantine is not required since the journey ends.)

Each of the next M lines contains three integers u, v, and w, indicating that there is a directed route from city u to city v with travel time w.

outputFormat

Output a single integer: the minimum total time required for Xiaoming to travel from city 1 to city N. If it is impossible to reach city N, output -1.

sample

5 6
0 1 2 3 4
1 2 5
2 3 5
3 5 5
1 4 10
4 5 2
2 5 15

15