/*
 * rainbowRoads_sjz.cpp
 *
 *  Created on: Oct 4, 2017
 *      Author: zeil
 */

#include <algorithm>
#include <functional>
#include <fstream>
#include <iostream>
#include <limits>
#include <list>
#include <set>
#include <queue>
#include <vector>


using namespace std;

int nAirports, nFlights;

typedef int Time;

struct Flight {
	int source;
	int dest;
	Time takeOff;
	Time arrival;
	Time expiration;
	long minPenalty;
	list<int>::iterator at;

	Flight() :
		source(-1), dest(-1), takeOff(-1), arrival(-1),
		expiration(numeric_limits<int>::max()),
		minPenalty(numeric_limits<int>::max())
	{
	}

};

ostream& operator<< (ostream& out, const Flight& f)
{
	out << "flt[" << f.source << "=>" << f.dest << ", "
			<< f.takeOff << ".." << f.arrival
			<< ", " << f.minPenalty
			<< " till " << f.expiration << "]";
	return out;
}



enum EventTypes {Arrival=0, Departure, Expiration};

struct Event {

	EventTypes kind;
	int time;
	int flightNum;

	void go();

	Event (EventTypes knd, int t, int f)
	: kind(knd), time(t), flightNum(f)
	{
	}


	bool operator< (const Event& e) const {
		if (time == e.time)
			return kind < e.kind;
		else
			return time < e.time;
	}

	bool operator> (const Event& e) const {
		return e < *this;
	}
	bool operator== (const Event& e) const {
		return time == e.time && kind == e.kind;
	}

	void arrival();
	void departure();
	void expiration();

};


Flight* flights;

ostream& operator<< (ostream& out, const Event& e)
{
	out << "ev[" << e.kind << ", " <<  e.time << ", ";
	out << flights[e.flightNum];
	out << "]";
	return out;
}



priority_queue<Event, vector<Event>, std::greater<Event> > pq;


struct Airport {
	list<int> priors;
};


Airport* airports;
int stoppingTime;
long bestSoFar;

void readFlights (istream& in)
{
	stoppingTime = 0;
	for (int i = 1; i <= nFlights; ++i)
	{
		Flight& f = flights[i];
		in >> f.source >> f.dest >> f.takeOff >> f.arrival;
		if (f.dest == nAirports) {
			stoppingTime = max(stoppingTime, f.arrival);
		}
		--f.source;
		--f.dest;
		pq.push(Event(Departure, f.takeOff, i));
	}
}

void Event::arrival()
{
	// On arrival to an airport, record the arrival time and penalty.
	// This may replace some old prior arrivals. It will cause others to be
	// scheduled for future removal.
	Flight& flight = flights[flightNum];
	Airport& port = airports[flight.dest];
	if (flight.dest == nAirports-1) {
		bestSoFar = min(bestSoFar, flight.minPenalty);
	}
	Time t = flight.arrival;
	for (list<int>::iterator it = port.priors.begin();
			it != port.priors.end(); ++it )
	{
		Flight& priorFlight = flights[*it];
		if (flight.arrival == priorFlight.arrival)
		{
			if (flight.minPenalty < priorFlight.minPenalty)
			{
				// cerr << "Dropping simultaneous flight " << priorFlight << endl;
				priorFlight.expiration = -1;
				it = port.priors.erase(it);
			} else
			{
				// cerr << "Dropping flight " << flight << " in favor of simultaneous " << priorFlight << endl;
				return;
			}
		}
		else if (flight.minPenalty <= priorFlight.minPenalty)
		{
			// cerr << "Dropping older flight " << priorFlight << endl;
			priorFlight.expiration = -1;
			it = port.priors.erase(it);
		} else if (priorFlight.expiration >= t) {
			long t0 = priorFlight.arrival;
			long t1 = t;
			long p0 = priorFlight.minPenalty;
			long p1 = flight.minPenalty;
			long texp =  ((t0*t0 - t1*t1) + (p0 - p1)) / (2*(t0 - t1));
			if (texp < priorFlight.expiration && texp > t)
			{
				// cerr << "Scheduling flight " << priorFlight << " to expire at " << texp << endl;
				priorFlight.expiration = *it;
				priorFlight.at = it;
				pq.push(Event(Expiration, texp+1, *it));
			}
		}
	}
	port.priors.push_back(flightNum);
}

void Event::departure()
{
	// On departure from an airport, compute the minimum penalty for
	// this departure and schedule an arrival with that penalty.
	Flight& flight = flights[flightNum];
	Airport& source = airports[flight.source];

	long minimum = numeric_limits<long>::max()/10000L;
	for (int priorFlightNum: source.priors)
	{
		Flight& priorFlight = flights[priorFlightNum];
		long t = time;
		long t0 = priorFlight.arrival;
		long wait = t - t0;
		long pen = priorFlight.minPenalty + wait*wait;
		minimum = min(minimum, pen);
	}
	if (minimum <= bestSoFar) {
		flight.minPenalty = minimum;
		pq.push(Event(Arrival, flight.arrival, flightNum));
	}
}

void Event::expiration()
{
	// On departure from an airport, compute the minimum penalty for
	// this departure and schedule an arrival with that penalty.
	Flight& flight = flights[flightNum];
	if (flight.expiration == time) {
		// cerr << "Expiring " << flight << " at time " << time << endl;
		flight.expiration = -1;
		airports[flight.dest].priors.erase(flight.at);
	}
}

void Event::go()
{
	if (kind == Arrival)
		arrival();
	else if (kind == Departure)
		departure();
	else
		expiration();
}



void runSimulation()
{
	bestSoFar = numeric_limits<long>::max();
	while (!pq.empty())
	{
		Event e = pq.top();
		if (e.time > stoppingTime) break;
		// cerr << e << endl;
		pq.pop();
		e.go();
	}
}


void solve (istream& in)
{
    in >> nAirports >> nFlights;
    airports = new Airport[nAirports];
    flights = new Flight[nFlights+1];
    readFlights(in);
    airports[0].priors.push_back(0);
    flights[0].minPenalty = 0;
    flights[0].arrival = 0;
    flights[0].dest = flights[0].source = 0;
    runSimulation();
    cout << bestSoFar << endl;
}


int main (int argc, char** argv)
{
	if (argc > 1) {
		ifstream in (argv[1]);
		solve(in);
	} else {
		solve (cin);
	}
}