A country has $n$ cities, and you need to travel from city $1$ to city $n$. There are $m$ two-way roads connecting the cities. You can travel multiple times along a road, but traveling will incur a certain cost. There exists a way to travel between any two cities.
You can buy or sell gold in all cities. In city $i$, you can buy or sell a bar of gold for the price $a_i$. Due to price differences between cities, you can make a profit by buying a bar of gold in one city and selling it in another. However, this is risky, and you will only do this at most once on your journey.
Determine the minimum cost to travel from city $1$ to city $n$.
### Input
- The first line contains two integers $n, m$.
- The second line contains $n$ integers $a_i$.
- The next $m$ lines, each line contains three integers $u, v, w$, representing a road connecting city $u$ and city $v$ with a travel cost of $w$.
### Output
- Print a single integer representing the minimum cost to complete the journey. The answer can be negative.
### Constraints
- $1 \le n, m \le 2 \times 10^5$.
- $1 \le u, v \le n$.
- $1 \le a_i, w \le 10^9$.
### Example
Input:
```
4 4
4 1 6 5
1 2 3
1 3 1
2 4 3
3 4 3
```
Output:
```
2
```
Explanation: You travel in the order $1 \rightarrow 2 \rightarrow 4$ with a cost of $6$. By buying gold in city $2$ and selling it in city $4$, you make a profit of $4$. The total minimum cost is $6 - 4 = 2$.
