#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, b;
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(r, l), c);
}
for (auto &i : MP) {
int t = i.ff;
sort(all(i.ss));
for (auto it = a.S.begin(); it != a.S.end();) {
if (it->ff > t) break;
a.S.erase(it++);
}
for (auto it = b.S.begin(); it != b.S.end();) {
if (it->ff > t) break;
b.S.erase(it++);
}
a.S.insert(pil(t, 0));
for (auto &j : i.ss) {
a.update(t + j.ff.ss, t + j.ff.ff, j.ss);
j.ff.ff = N + 1 - j.ff.ff;
j.ff.ss = N + 1 - j.ff.ss;
swap(j.ff.ff, j.ff.ss);
}
sort(all(i.ss));
b.S.insert(pil(t, 0));
for (auto &j : i.ss) b.update(t + j.ff.ss, t + j.ff.ff, j.ss);
if (a.S.rbegin()->ff - t >= N - (b.S.rbegin()->ff - t)) {
for (auto x : b.S) {
auto it = a.S.lower_bound(pil(N - (x.ff - t) + t, 0));
if (it != a.S.end()) ans = min(ans, it->ss + x.ss);
}
}
}
if (ans == INF) ans = -1;
cout << ans;
return 0;
}
