Problem Description

Country A has $N$ cities, numbered $1 \ldots N$. Xiaoming is an employee of a company located in city $1$. Today, he suddenly received a notice from his supervisor that he needs to go on a business trip to city $N$.

Due to the pandemic, many direct transportation options are temporarily shut down. Xiaoming cannot take a plane directly from city $1$ to city $N$, and must transfer by land transportation through other cities. Through a transportation information network, he found $M$ routes between cities that are still open, along with the time required for each route.

Also due to the pandemic, after arriving at a city, Xiaoming must stay in quarantine for a period of time before he can leave that city to travel to other cities. He also found the quarantine information for each city online. (Since Xiaoming was previously in city $1$, he can leave city $1$ directly and does not need to quarantine.)

Because his supervisor requires it, Xiaoming wants to reach city $N$ as quickly as possible. So he asks you for help, hoping you can plan a route that allows him to arrive at city $N$ in the shortest time.

Input Format

Line $1$: Two positive integers $N, M$, where $N$ is the number of cities in Country A, and $M$ is the number of routes that have not been closed.

Line $2$: $N$ positive integers. The $i$-th integer $C_i$ means the quarantine time required after arriving at city $\mathrm{i}$.

Lines $3 \ldots M+2$: Each line contains three positive integers $u, v, c$, meaning there is a bidirectional route between city $u$ and city $v$ that is still open, and the travel time on this route is $c$.

Output Format

Line $1$: One positive integer, the shortest time for Xiaoming to start from city $1$ and arrive at city $N$. (After arriving at city $N$, the quarantine time of city $N$ does not need to be counted.)

4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5

13

Hint

[Sample Explanation]

[Testdata Scale and Rules]

For $100\%$ of the testdata, $1 \leq N \leq 1000, 1 \leq M \leq 10000, 1 \leq C_i \leq 200, 1 \leq u, v \leq N, 1 \leq c \leq 1000$.

Lanqiao Cup 2022 National Contest B Group, Problem E.

Translated by ChatGPT 5