Avoiding Airports

David is planning a trip around the world. He can visit $n$ countries, and $m$ flights are available to him. Flight $i$ leaves country $a_i$ at time $s_i$ and lands in country $b_i$ at time $e_i$.

David is in the airport of country $1$ at time $0$, and he wants to reach country $n$. The total time the trip takes does not bother him, but he hates waiting in an airport. Waiting $t$ units of time in an airport gives him $t^2$ units of frustration. The time he spends in the airport of country $1$ from time $0$ until his first flight departs counts as waiting too.

Find an itinerary that minimizes the total frustration.

The first line contains two space separated integers $n$ and $m$. ($2 \le n \le 200\,000$, $1 \le 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$) This describes a flight from country $a_i$ to country $b_i$ that departs at time $s_i$ and lands at time $e_i$.

A flight might have the same departure and arrival country.

No two flights have the same departure time, and no two flights have the same arrival time. No flight has the same arrival time as the departure time of another flight. There is always a way for David to reach country $n$.

Print the minimum total frustration on a single line.

In the first example the cheapest itinerary is this one.

• The fifth flight of the input. It goes from country $1$ to country $2$, departing at time $3$ and landing at time $8$.
• The third flight. It goes from country $2$ to country $1$, departing at time $9$ and landing at time $12$.
• The seventh flight. It goes from country $1$ to country $3$, departing at time $13$ and landing at time $27$.
• The eighth flight. It goes from country $3$ to country $5$, departing at time $28$ and landing at time $100$.

The four waits cost $3^2$, $1^2$, $1^2$, and $1^2$, so the total frustration is $12$. Another itinerary gets David to his destination sooner, but its total frustration is higher.