#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
struct Endpoint
{
int x, y, segment, color;
bool operator <(const Endpoint &other) const
{
if (x != other.x)
return (x < other.x);
return (color < other.color);
}
};
struct Edge
{
Edge(int d, long long w) : dest(d), weight(w) {}
int dest;
long long weight;
bool operator <(const Edge &other) const
{
return (other.weight < weight);
}
};
const int MAXN = 1e5;
const int MAXG = 2e6;
const long long INFTY = 1e18;
int day[MAXN];
int left[MAXN], right[MAXN];
long long cost[MAXN];
Endpoint extr[2 * MAXN];
Endpoint bckp[2 * MAXN];
int nodes;
std::vector<Edge> graph[MAXG];
std::priority_queue<Edge> dijkstra;
long long minDist[MAXG];
void buildgraph(int first, int last)
{
if (last - first == 1)
return;
int mid = (first + last) / 2;
buildgraph(first, mid);
buildgraph(mid, last);
int previous = -1;
int iLeft = first, iSort = first;
for (int iRight = mid; iRight < last; iRight++)
{
while (iLeft < mid && extr[iLeft].y >= extr[iRight].y)
{
if (extr[iLeft].color == 0)
{
graph[nodes].emplace_back(extr[iLeft].segment, cost[extr[iLeft].segment]);
if (previous != -1)
graph[nodes].emplace_back(previous, 0);
previous = nodes;
nodes++;
}
bckp[iSort] = extr[iLeft];
iLeft++; iSort++;
}
if (extr[iRight].color == 1 && previous != -1)
graph[extr[iRight].segment].emplace_back(previous, 0);
bckp[iSort] = extr[iRight];
iSort++;
}
for (; iLeft < mid; iLeft++)
{
bckp[iSort] = extr[iLeft];
iSort++;
}
for (int iCpy = first; iCpy < last; iCpy++)
extr[iCpy] = bckp[iCpy];
}
void push(int node, long long dist)
{
for (Edge &edge : graph[node])
if (minDist[edge.dest] == INFTY)
{
minDist[edge.dest] = dist + edge.weight;
if (edge.weight == 0)
push(edge.dest, dist);
else
dijkstra.emplace(edge.dest, dist + edge.weight);
}
}
long long findcost(int people, int treatments)
{
std::fill_n(minDist, MAXG, INFTY);
for (int iTreat = 0; iTreat < treatments; iTreat++)
if (left[iTreat] == 1)
{
minDist[iTreat] = cost[iTreat];
dijkstra.emplace(iTreat, cost[iTreat]);
}
while (!dijkstra.empty())
{
int node = dijkstra.top().dest;
long long dist = dijkstra.top().weight;
dijkstra.pop();
push(node, dist);
}
long long minCost = INFTY;
for (int iTreat = 0; iTreat < treatments; iTreat++)
if (right[iTreat] == people)
minCost = std::min(minCost, minDist[iTreat]);
return minCost;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
int people, treatments;
std::cin >> people >> treatments;
for (int iTreat = 0; iTreat < treatments; iTreat++)
{
std::cin >> day[iTreat] >> left[iTreat] >> right[iTreat] >> cost[iTreat];
extr[iTreat * 2].x = day[iTreat] + left[iTreat];
extr[iTreat * 2].y = day[iTreat] - left[iTreat];
extr[iTreat * 2].segment = iTreat;
extr[iTreat * 2].color = 0;
extr[iTreat * 2 + 1].x = day[iTreat] + right[iTreat] + 1;
extr[iTreat * 2 + 1].y = day[iTreat] - right[iTreat] - 1;
extr[iTreat * 2 + 1].segment = iTreat;
extr[iTreat * 2 + 1].color = 1;
}
std::sort(extr, extr + 2 * treatments);
nodes = 2 * treatments;
buildgraph(0, 2 * treatments);
long long minpay = findcost(people, treatments);
if (minpay == INFTY)
std::cout << "-1\n";
else
std::cout << minpay << '\n';
return 0;
}
