408179: GYM103037 J Bohemian Rhapsody

Mreddie Fercury is the vocalist for the locally famous Queen cover band, and he has been invited to perform his namesake's biggest hits in Moscow. It is quite a far distance from his hometown of Austin, which means Mreddie must travel via a series of flights. Although Mreddie does not particularly enjoy flying, he gets the most overanxious while waiting in airports. Every time he has a layover of $$$t$$$ minutes, his anxiousness increases by $$$t^2$$$ units.

We will define a layover as a contiguous period of time between the arrival of a flight and the departure of the next flight Mreddie boards, or the start of his journey (considered to be minute $$$0$$$) and the first flight Mreddie departs on.

Our protagonist is currently at airport $$$1$$$ in Austin and wants to travel to airport $$$N$$$ in Moscow using some series of the $$$M$$$ flights available to him. Since the total amount of time taken to travel to Moscow does not matter to Mreddie, he will even take flights that go back to the airport he started in to avoid time spent on the ground!

You, Mreddie's travel agent, need to find a sequence of flights that Mreddie can take to make it to Moscow while minimizing the units of anxiousness he accumulates while traveling. Good luck!

The first line of input contains two space-separated integers $$$N$$$ and $$$M$$$ ($$$1 \leq N, M \leq 200000$$$) representing the number of airports and the number of available flights, respectively. Each of the next $$$M$$$ lines contains four space-separated integers $$$a$$$, $$$b$$$, $$$c$$$, and $$$d$$$ ($$$1 \leq a, b \leq N$$$, $$$0 \leq c \leq d \leq 10^9$$$) representing the departure airport, arrival airport, departure time (in minutes), and arrival time (in minutes), respectively.

All ordered pairs of flights have different departure times and different arrival times, and the departure time of one flight will be different from the arrival time of the other. For every flight, at least one of $$$a \neq b$$$ and $$$c \neq d$$$ will be true.

Output the minimum possible anxiousness level Mreddie will have to deal with if an optimal sequence of flights is chosen. If there is no sequence of flights that Mreddie can take to get from Austin to Moscow, then output $$$-1$$$.

4 5
1 3 40 50
3 3 70 100
3 4 110 1337
1 2 20 20
2 4 300 420

2100