#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define ff first
#define ss second
#define eack emplace_back
#define all(x) (x).begin(), (x).end()
const ll INF = 1e18;
int N, M;
ll ans = INF;
map<int, vector<pair<pii, int>>> MP;
struct X {
set<pil> S;
void add(pil v) {
auto it = S.lower_bound(pil(v.ff, 0));
if (it != S.end() && it->ss <= v.ss) return;
if (it == S.begin()) {
if (it->ff == v.ff) S.erase(it);
S.insert(v);
return;
}
if (it->ff == v.ff) S.erase(it--);
else --it;
while (1) {
if (it->ss >= v.ss) {
if (it == S.begin()) {
S.erase(it);
break;
}
S.erase(it--);
}
else break;
}
S.insert(v);
}
void update(int s, int e, int v) {
auto it = S.lower_bound(pil(s - 1, 0));
if (it == S.end()) return;
add(pil(e, it->ss + v));
}
} a;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= M; ++i) {
int t, l, r, c; cin >> t >> l >> r >> c;
MP[t].eack(pii(l, r), c);
}
vector<pair<pii, pii>> vec;
for (auto &i : MP) {
int t = i.ff;
for (auto j : i.ss) vec.eack(pii(t, j.ss), j.ff);
vector<pair<pii, int>> v;
for (auto j : vec) v.eack(pii(j.ss.ss == N ? N : j.ss.ss - t + j.ff.ff, j.ss.ff == 1 ? 1 : j.ss.ff + t - j.ff.ff), j.ff.ss);
sort(all(v));
a.S.clear();
a.S.insert(pil(0, 0));
for (auto i : v) if (i.ff.ss < i.ff.ff) a.update(i.ff.ss, i.ff.ff, i.ss);
auto it = a.S.lower_bound(pil(N, 0));
if (it != a.S.end()) ans = min(ans, it->ss);
}
if (ans == INF) ans = -1;
cout << ans;
return 0;
}
