David is looking to book some travel over the world.
There are
$n$ countries
that he can visit, and
$m$
flights that are available. The
$i$th flight goes from country
$a_ i$ to country
$b_ i$. It departs at time
$s_ i$, and lands at time
$e_ i$.
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 spaceseparated
integers $n$ and
$m$ ($1 \le n,m \le 200\, 000$).
Each of the next $m$
lines contains four spaceseparated 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.
Sample Input 1 
Sample Output 1 
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

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

1900
