/*input
10 5
2 5 10 3
1 1 6 5
5 2 8 3
7 6 10 4
4 1 3 1
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <time.h>
using namespace std;
const int64_t INFLL = 1e17;
const int MAXN = 100007, INF = 2e9 + 9;
int N, M, T[MAXN], R[MAXN], L[MAXN], C[MAXN];
int64_t dist[MAXN];
struct Point
{
int x, y, id;
Point (int _x, int _y, int _id): x(_x), y(_y), id(_id) {}
};
// bool compY(const Point &p, const Point &q) { return p.y == q.y ? p.x < q.x : p.y < q.y; }
vector<Point> pnts;
int min_y[MAXN << 2];
priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, greater<pair<int64_t, int>>> pq;
void build(int rt = 1, int lo = 0, int hi = M - 1)
{
if (lo == hi) {
min_y[rt] = pnts[lo].y;
return;
}
int md = (lo + hi) >> 1;
build(rt << 1, lo, md);
build(rt << 1 | 1, md + 1, hi);
min_y[rt] = min(min_y[rt << 1], min_y[rt << 1 | 1]);
}
void upd(int rx, int ry, int64_t val, int rt = 1, int lo = 0, int hi = M - 1)
{
if (rx < pnts[lo].x || min_y[rt] > ry) return;
if (pnts[hi].x <= rx && lo == hi) {
int id = pnts[lo].id;
if (dist[id] > val + C[id]) {
dist[id] = val + C[id];
pq.emplace(dist[id], id);
}
min_y[rt] = INF;
return;
}
int md = (lo + hi) >> 1;
upd(rx, ry, val, rt << 1, lo, md);
upd(rx, ry, val, rt << 1 | 1, md + 1, hi);
min_y[rt] = min(min_y[rt << 1], min_y[rt << 1 | 1]);
}
int main()
{
// freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> M;
pnts.reserve(M);
for (int i = 1; i <= M; ++i) {
cin >> T[i] >> L[i] >> R[i] >> C[i];
pnts.emplace_back(L[i] - T[i], L[i] + T[i], i);
}
sort(pnts.begin(), pnts.end(), [&](const Point &p, const Point &q) { return p.x == q.x ? p.y < q.y : p.x < q.x; });
build();
for (int i = 1; i <= M; ++i) {
if (L[i] == 1) {
dist[i] = C[i];
pq.emplace(dist[i], i);
} else {
dist[i] = INFLL;
}
}
while (!pq.empty()) {
int u = pq.top().second;
assert(dist[u] == pq.top().first);
pq.pop();
upd(1 + R[u] - T[u], 1 + R[u] + T[u], dist[u]);
}
int64_t ans = INFLL;
for (int i = 1; i <= M; ++i) if (R[i] == N) {
ans = min(ans, dist[i]);
}
if (ans == INFLL) ans = -1;
cout << ans << endl;
cerr << 1.0 * clock() / CLOCKS_PER_SEC << endl;
}
