Reimu is preparing to host a Hanami 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 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 costs $l_i$ ($l_i \le w_i$).
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 Hanami.
### Input
- The first line contains two integer $n,m$.
- The second line contains $n$ integer $c_i$.
- The next $m$ lines, each line contains four integer $u,v,w,l$, there is a route between $u$ and $v$, costs $w_i$ for the first time, and $l_i$ for the second time and onwards.
### 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 l_i \le w_i \le 10^9$.
- $1 \le c_i \le 10^9$.
### Example
Input:
```
5 6
10 10 1 10 10
1 2 2 2
2 3 1 1
3 4 1 1
4 5 2 2
1 5 1 1
2 5 2 0
```
Output:
```
6
```
