#include <bits/stdc++.h>
using i64 = long long;
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
constexpr i64 inf = i64(1E18);
template<typename T>
bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::vector<std::array<i64, 4>> A(M);
for (int i = 0; i < M; ++i) {
std::cin >> A[i][0] >> A[i][1] >> A[i][2] >> A[i][3];
A[i][2] += 1;
}
std::sort(A.begin(), A.end(), [&](auto lhs, auto rhs) -> bool {
return lhs[1] - lhs[0] < rhs[1] - rhs[0];
});
debug(A);
#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l) << 1)
std::vector<i64> f(M, inf);
min_pq<std::pair<i64, int>> pq;
std::vector<std::vector<int>> tree(M << 1);
std::vector<int> ptr(M << 1);
auto build = [&](auto&& self, int v, int l, int r) -> void {
if (l + 1 == r) {
tree[v] = {l};
return;
}
def;
self(self, lv, l, mid);
self(self, rv, mid, r);
tree[v].resize(r - l);
int p0 = 0, p1 = 0;
while (p0 != mid - l && p1 != r - mid) {
if (A[tree[lv][p0]][1] + A[tree[lv][p0]][0] <= A[tree[rv][p1]][1] + A[tree[rv][p1]][0]) {
tree[v][p0 + p1] = tree[lv][p0];
p0++;
} else {
tree[v][p0 + p1] = tree[rv][p1];
p1++;
}
}
while (p0 != mid - l) {
tree[v][p0 + p1] = tree[lv][p0];
p0++;
}
while (p1 != r - mid) {
tree[v][p0 + p1] = tree[rv][p1];
p1++;
}
};
build(build, 0, 0, M);
auto modify = [&](auto&& self, int v, int l, int r, i64 ql, i64 qr, i64 x) -> void {
if (A[l][1] - A[l][0] > ql) {
return;
}
if (A[r - 1][1] - A[r - 1][0] <= ql) {
int& p = ptr[v];
while (p != r - l && A[tree[v][p]][1] + A[tree[v][p]][0] <= qr) {
if (chmin(f[tree[v][p]], x + A[tree[v][p]][3])) {
pq.emplace(f[tree[v][p]], tree[v][p]);
}
p++;
}
return;
}
def;
self(self, lv, l, mid, ql, qr, x);
self(self, rv, mid, r, ql, qr, x);
};
i64 ans = inf;
for (int i = 0; i < M; ++i) {
if (A[i][1] == 1) {
if (chmin(f[i], A[i][3])) {
pq.emplace(f[i], i);
}
}
}
while (!pq.empty()) {
auto[x, i] = pq.top();
pq.pop();
if (f[i] != x) {
continue;
}
debug(i, f[i]);
if (A[i][2] == N + 1) {
chmin(ans, f[i]);
}
modify(modify, 0, 0, M, A[i][2] - A[i][0], A[i][2] + A[i][0], f[i]);
// for (int j = 0; j < M; ++j) {
// if (A[j][1] - A[j][0] <= A[i][2] - A[i][0] && A[j][1] + A[j][0] <= A[i][2] + A[i][0]) {
// if (chmin(f[j], f[i] + A[j][3])) {
// pq.emplace(f[j], j);
// }
// }
// }
}
if (ans >= inf) {
ans = -1;
}
std::cout << ans << '\n';
return 0;
}
