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 ci. 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 wi. However, due to the system's unique rules, subsequent uses of the same route costs li (li≤wi).
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 ci.
- The next m lines, each line contains four integer u,v,w,l, there is a route between u and v, costs wi for the first time, and li for the second time and onwards.
### Output
- Print an integer, the minimum cost.
### Constraints
- 1≤n,m≤105.
- 1≤u,v≤n,u≠v.
- 1≤li≤wi≤109.
- 1≤ci≤109.
### Example
Input:
56101011010122223113411452215112520
Output:
6
