// https://oj.uz/problem/view/JOI20_treatment
#include <bits/stdc++.h>
using namespace std;
namespace std {
template <int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
static_assert(D >= 1, "Dimension must be positive");
template <typename... Args>
Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};
template <typename T>
struct Vec<1, T> : public vector<T> {
Vec(int n = 0, T val = T()) : std::vector<T>(n, val) {}
};
/* Example
Vec<4, int64_t> f(n, k, 2, 2); // = f[n][k][2][2];
Vec<2, int> adj(n); // graph
*/
template <class Fun>
class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}
template <class... Args>
decltype(auto) operator()(Args &&...args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
/* Example
auto fun = y_combinator([&](auto self, int x) -> void {
self(x + 1);
});
*/
} // namespace std
vector<int> c;
vector<int64_t> d;
priority_queue<pair<int64_t, int>> pq;
struct segment_tree {
int n;
vector<vector<pair<int, int>>> val;
vector<int> done;
segment_tree(int n, const vector<pair<int, int>> &a) : n(n), val(n * 4), done(n, 0) {
build(1, 0, n - 1, a);
rev(1, 0, n - 1);
}
void build(int v, int l, int r, const vector<pair<int, int>> &a) {
if (l == r) {
val[v] = {a[l]};
return;
}
int mid = (l + r) / 2;
build(v * 2, l, mid, a);
build(v * 2 + 1, mid + 1, r, a);
merge(val[v * 2].begin(), val[v * 2].end(), val[v * 2 + 1].begin(), val[v * 2 + 1].end(),
back_inserter(val[v]));
}
void rev(int v, int l, int r) {
reverse(val[v].begin(), val[v].end());
if (l == r) return;
int mid = (l + r) / 2;
rev(v * 2, l, mid);
rev(v * 2 + 1, mid + 1, r);
}
void update(int l, int r, int x, int64_t du) {
update(1, 0, n - 1, l, r, x, du);
}
void update(int v, int l, int r, int s, int t, int x, int64_t du) {
if (l > t || r < s) return;
if (s <= l && r <= t) {
while (val[v].size() && val[v].back().first <= x) {
auto [value, index] = val[v].back();
val[v].pop_back();
if (done[index]) continue;
done[index] = 1;
if (d[index] > du + c[index]) {
d[index] = du + c[index];
pq.emplace(-d[index], index);
}
}
return;
}
int mid = (l + r) / 2;
update(v * 2, l, mid, s, t, x, du);
update(v * 2 + 1, mid + 1, r, s, t, x, du);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> l(m), r(m), t(m);
c.resize(m);
for (int i = 0; i < m; i++) cin >> t[i] >> l[i] >> r[i] >> c[i];
for (int i = 0; i < m; i++) l[i]--;
d.assign(m, 1e18);
for (int i = 0; i < m; i++) {
if (l[i] == 0) {
d[i] = c[i];
pq.emplace(-d[i], i);
}
}
vector<pair<int, int>> tmp(m);
for (int i = 0; i < m; i++) tmp[i] = make_pair(l[i] + t[i], i);
sort(tmp.begin(), tmp.end(), [&](auto a, auto b) { return t[a.second] < t[b.second]; });
segment_tree seg_less(m, tmp);
for (int i = 0; i < m; i++) tmp[i] = make_pair(l[i] - t[i], i);
sort(tmp.begin(), tmp.end(), [&](auto a, auto b) { return t[a.second] < t[b.second]; });
segment_tree seg_greater(m, tmp);
vector<int> ord(m);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](auto a, auto b) { return t[a] < t[b]; });
vector<int> p(m);
for (int i = 0; i < m; i++) p[ord[i]] = i;
// if t[j] >= t[i] : l[j] <= r[i] - (t[j] - t[i])
// l[j] + t[j] <= r[i] + t[i]
// if t[j] <= t[i] : l[j] <= r[i] - (t[i] - t[j])
// l[j] - t[j] <= r[i] - t[i]
while (pq.size()) {
auto [du, j] = pq.top();
pq.pop();
du = -du;
if (du != d[j]) continue;
if (r[j] == n) {
cout << du;
return 0;
}
seg_less.update(p[j], m - 1, r[j] + t[j], du);
seg_greater.update(0, p[j], r[j] - t[j], du);
}
cout << -1;
}
