Jacek wants to fly around the world. Unfortunately, he does not have much money, so he wants to do it as cheaply as possible. Jacek realized that Bajtolinie Lotnicze flights are relatively cheap, so he checked all the connections in their offer. He is now sitting over a map and planning. Help him!

Jacek's data consists of a list of $n$ cities and a list of $m$ connections between these cities. For each city, Jacek knows its longitude. Each flight connects two cities and allows travel in both directions - if we can fly from city $a$ to city $b$ for $x$ bajtalars, then the trip from city $b$ to city $a$ is also possible and costs $x$ bajtalars.

For each connection, we know whether the planes performing this connection fly west or east (we assume that no two cities have the same longitude). Each plane flies directly to its destination, and no flight route passes over the pole or circles the Earth completely (i.e., the plane travels less than 360° of longitude).

Another problem has arisen. What does it mean to "fly around the world"? Jacek decided that he wants the total number of degrees of longitude traveled eastward during the entire trip to be different from the number of degrees traveled westward. Jacek plans to start and end his trip in his hometown.

Consider the following examples (assuming in them that all flights are in a reasonable direction, i.e., the one in which we fly less than 180 degrees):

• the flight Warsaw (21°E) - Moscow (37°E) - Tokyo (139°E) - Los Angeles (118°W) - New York (73°W) - Warsaw (21°E) is a flight around the world (during the entire trip we fly east);
• the flight Warsaw (21°E) - Moscow (37°E) - Tokyo (139°E) - Los Angeles (118°W) - Miami (80°W) - Cairo (31°E) - Dublin (6°W) - Warsaw (21°E) is also a flight around the world (we fly over 360° east, while we only fly west during the flight from Cairo to Dublin);
• the flight Warsaw (21°E) - Moscow (37°E) - Singapore (103°E) - Los Angeles (118°W) - Miami (80°W) - Cairo (31°E) - Delhi (77°E) - Sydney (151°E) - Buenos Aires (58°W) - Johannesburg (28°E) - Warsaw (21°E) is a flight around the world (we travel over 720° east, while we only travel a few degrees west during the flight from Johannesburg to Warsaw);
• the flight Warsaw (21°E) - Moscow (37°E) - Singapore (103°E) - Los Angeles (118°W) - Miami (80°W) - Cairo (31°E) - Johannesburg (28°E) - Buenos Aires (58°W) - Sydney (151°E) - Delhi (77°E) - Kiev (30°E) - Warsaw (21°E) is not a flight around the world (the number of degrees traveled eastward is exactly the same as the number of degrees flown westward).

Input

The first line of input contains two integers $n$ and $m$ ($2 \le n \le 100\,000$, $1 \le m \le 200\,000$) representing the number of cities on Jacek's map and the number of flights available in Bajtolinie Lotnicze, respectively. The cities are numbered from 1 to $n$. Jacek starts his trip in city number 1. The second line contains the coordinates of the cities given as a sequence of integers $w_1, \ldots, w_n$ ($0 \le w_{i} \le 1\,296\,000$). The number $w_{i}$ indicates how many geographic seconds east of the prime meridian city number $i$ is located (1 second is 1/3600 of a degree). No two cities have the same longitude.

Each of the next $m$ lines describes one flight. The $i$-th of these lines contains four integers $a_{i}$, $b_{i}$, $x_{i}$, $k_{i}$ ($1 \le a_{i}, b_{i} \le n$, $a_{i} \ne b_{i}$, $1 \le x_{i} \le 5\,000$, $k_{i} \in \{-1, 1\}$). They mean that Bajtolinie offers flights between cities $a_{i}$ and $b_{i}$ at a cost of $x_{i}$ bajtalars, and the flight route from city $a_{i}$ to city $b_{i}$ leads east (when $k_{i} = 1$) or west (when $k_{i} = -1$). The return flight route leads in the opposite direction.

Output

Your program should output the cost (in bajtalars) of the cheapest trip around the world that starts and ends in city number 1. If no such trip exists, the program should output -1.

Examples

Input 1

5 7
75630 135420 502890 1029600 870750
4 3 1 1
3 2 4 -1
3 5 7 1
1 5 15 1
1 4 10 -1
1 2 2 1
5 4 3 1

Output 1

23