Problem Description

In the AtCoder Kingdom, there are $N$ cities numbered $1, 2, \ldots, N$, and $M$ bidirectional roads connecting these cities. Each road $i$ connects city $U_i$ and city $V_i$, and it takes $T_i$ hours to travel from one city to the other. Additionally, each city has a numerical value called scenery, where the scenery of city $i$ is $A_i$. When traveling from one city to another via one or more roads, the time taken for the journey is the sum of the travel times of the roads used, and the satisfaction of the journey is the sum of the sceneries of the cities passed through, including the starting and ending cities. Note that if a city is passed through more than once, its scenery is only counted once for the satisfaction.

Takahashi is currently in city $1$ and wants to travel to city $N$. Since he is in a hurry, he wants to minimize the travel time while maximizing the satisfaction of the journey. Determine the satisfaction of Takahashi's journey.

Input Format

The input is given from the standard input in the following format:

$N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$ $U_1$ $V_1$ $T_1$ $U_2$ $V_2$ $T_2$ $:$ $U_M$ $V_M$ $T_M$

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

12

Sample Input #2

6 5
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

Sample Output #2

6000000000

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $N-1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq U_i, V_i \leq N$
• $U_i \neq V_i$
• $1 \leq T_i \leq 10^9$
• All inputs are integers
• Any two cities can be connected via some roads

Sample Explanation 1

Traveling $1 \to 2 \to 4$ takes the shortest time of $5$ hours, and the satisfaction is $10$. Traveling $1 \to 3 \to 4$ also takes the shortest time of $5$ hours, and the satisfaction is $12$. There are no other ways to travel with a time of $5$ hours. For example, traveling $1 \to 2 \to 3 \to 4$ has a satisfaction of $17$ but takes $6$ hours, which is not the shortest. Also, there is no way to travel from city $1$ to city $4$ in $4$ hours or less. Therefore, the answer is $12$.

Sample Explanation 2

Note that the answer may not fit within a 32-bit integer.

见题面 Input 部分

见题面 Output 部分