Problem J
Hittast

Image from icelandair.com with permission

Álfur and Benedikt are in love and want nothing more than to spend their time together. Sadly, they don’t live close to each other. Álfur lives in Helsinki but Benedikt lives in Buenos Aires. So they can’t meet up whenever they want. They decided to coordinate where and when to meet up next.

A date has been decided, but not a location. They have no preference for location, as long as they are together. But Álfur is a university student, so his budget is limited. They’ve asked you to find the cheapest solution for them.

Benedikt has written down all possible meeting locations and found the cheapest lodging option at each location. He also found various different travel options between the locations. Álfur and Benedikt have different credit cards, so they may not get the same prices. Can you use this information to find the cheapest option for these love birds.

Input

The first line of the input contains two integers $n$ ($2 \leq n \leq 10^5$), the number of locations, and $m$ ($1 \leq m \leq 10^5$), the number of travel options between locations. Helsinki is location $1$ and Buenos Aires is location $n$. The second line contains $n$ integers, $g_1, \dotsc , g_ n$, where $g_ i$ is the lodging price at location $i$.

The follow $m$ lines, each containing four integers $u$, $v$, $a$ and $b$, indicating that you can travel from $u$ and $v$ in both directions, that the cost for Álfur is $a$, and that the cost for Benedikt is $b$. We have $1 \leq u, v \leq n$ and $u \neq v$. Benedikt was only interested in the cheapest travel option between the locations, so each pair $u, v$ appears at most once.

All prices in the input are at least $0$ and at most $10^4$.

You may assume that all locations are reachable from all other locations.

Output

Print a single integer, the cheapest cost for Álfur and Benedikt to meet.

Scoring

2 1
10 1
1 2 50 60

51

4 6
1000 400 450 900
3 4 0 0
1 2 0 0
1 4 0 0
3 1 0 0
2 3 0 0
4 2 0 0

400

4 6
0 4 5 0
3 4 1 2
1 2 2 3
1 4 9 9
3 1 3 3
2 3 2 1
4 2 5 3

4