Today is the joyous Tanabata day, and Reimu is preparing to host a festival at Hakurei Shrine. Excited to join in the festivities, Marisa decides to make the day even more memorable by purchasing a sake bottle as a special gift.
There are a total of $n$ unique places where Marisa can buy sake, each with its own price denoted by $c_i$. To navigate between these places, Marisa can utilize a special two-way transportation system operated by the Kappa. However, there are certain costs associated with using each route. The first time Marisa uses route $i$, it incurs a cost of $w_i$. However, due to the system's unique rules, subsequent uses of the same route will be free.
Marisa devises a plan to begin her journey from her house at location $1$, explore different places to find the perfect sake, and ultimately reach the Hakurei Shrine located at location $n$. The goal is to determine the minimum cost for Marisa to accomplish her plan and fully enjoy the Tanabata festival.
### Input
- The first line contains two integer $n,m$.
- The second line contains $n$ integer $c_i$.
- The next $m$ lines, each line contains three integer $u,v,w$, there is a route between $u$ and $v$ and costs $w_i$ for the first time.
### Output
- Print an integer, the minimum cost.
### Constraints
- $1 \le n,m \le 10^5$.
- $1 \le u, v \le n, u \neq v$.
- $1 \le w_i,c_i \le 10^9$.
### Example
Input:
```
5 6
10 10 1 10 10
1 2 2
2 3 1
3 4 1
4 5 2
1 5 1
2 5 2
```
Output:
```
5
```
