Problem D
Avoiding Airports

David is currently at the airport in country $1$, and the current time is $0$, and he would like to travel country $n$. He does not care about the total amount of time needed to travel, but he really hates waiting in the airport. If he waits $t$ seconds in an airport, he gains $t^2$ units of frustration. Help him find an itinerary that minimizes the sum of frustration.

Input

The first line of input contains two space-separated integers $n$ and $m$ ($1 \le n,m \le 200\, 000$).

Each of the next $m$ lines contains four space-separated integers $a_ i$, $b_ i$, $s_ i$, and $e_ i$ ($1 \le a_ i, b_ i \le n$; $0 \le s_ i \le e_ i \le 10^6$).

A flight might have the same departure and arrival country.

No two flights will have the same arrival time, or have the same departure time. In addition, no flight will have the same arrival time as the departure time of another flight. Finally, it is guaranteed that there will always be a way for David to arrive at his destination.

Output

Print, on a single line, the minimum sum of frustration.

Examples

In the first sample, it is optimal to take this sequence of flights:

• Flight $5$. Goes from airport $1$ to airport $2$, departing at time $3$, arriving at time $8$.

• Flight $3$. Goes from airport $2$ to airport $1$, departing at time $9$, arriving at time $12$.

• Flight $7$. Goes from airport $1$ to airport $3$, departing at time $13$, arriving at time $27$.

• Flight $8$. Goes from airport $3$ to airport $5$, deparing at time $28$, arriving at time $100$.

The frustration for each flight is $3^2, 1^2, 1^2,$ and $1^2$, respectively. Thus, the total frustration is $12$.

Note that there is an itinerary that gets David to his destination faster. However, that itinerary has a higher total frustration.

5 8
1 2 1 10
2 4 11 16
2 1 9 12
3 5 28 100
1 2 3 8
4 3 20 21
1 3 13 27
3 5 23 24

12

3 5
1 1 10 20
1 2 30 40
1 2 50 60
1 2 70 80
2 3 90 95

1900