\documentclass{article}

\usepackage{geometry}
\usepackage{verbatim}
\usepackage{tabularx}
\usepackage{graphicx}
\usepackage{etoolbox}

\ifdefined\testinputfile\endcsname\else\input ../pacnw/ReadSamples.tex\fi

\title{Avoiding Airports}
\problemname{avoidingairports}
\date{}

\begin{document}
\maketitle
\begin{figure}[h!]
\centering
\includegraphics[width=0.4\textwidth]{avoidingairports.png}
\end{figure}

David is looking to book some travel all 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 in the airport in country 1, and the current time is 0,
and he would like to travel to 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$ time units in an airport,
he gains $t^2$ units of frustration.
Help him find an itinerary that minimizes the total frustration.

\section{Input}

The first line of input 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 arrives at time $e_i$.

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.

\section{Output}

Print, on a single line, the minimum total frustration.

In the first sample, it is optimal to take this sequence of flights:
\begin{itemize}
\item Flight 5. Goes from airport 1 to airport 2, departing at time 3, arriving at time 8.
\item Flight 3. Goes from airport 2 to airport 1, departing at time 9, arriving at time 12.
\item Flight 7. Goes from airport 1 to airport 3, departing at time 13, arriving at time 27.
\item Flight 8. Goes from airport 3 to airport 5, deparing at time 28, arriving at time 100.
\end{itemize}
The frustration for each wait 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.

\sampleio{avoidingairports}

\end{document}
