#include <bits/stdc++.h>
using namespace std;
#define int long long
int INF = 1e18;
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
int N, M; cin >> N >> M;
array<int, 4> a[M];
int c[M], p {};
for(auto &[R, L, T, C] : a) {
cin >> T >> L >> R >> C;
c[p++] = T;
}
sort(a, a + M);
sort(c, c + M);
set<array<int, 2>> s[2][M + 1];
int ans = INF;
for(auto [R, L, T, C] : a) {
int cur = L < 2 ? 0 : INF, t = lower_bound(c, c + M, T) - c;
for(int i = 0; i < 2; ++i) {
int f = L + (i ? T : -T) - 1;
for(int k = (i ? t + 1 : M - t); k > 0; k -= k&-k) {
if(!empty(s[i][k]) && f <= (*--end(s[i][k]))[0])
cur = min(cur, (*s[i][k].lower_bound({f}))[1]);
}
}
cur = min(cur + C, INF);
if(R == N) ans = min(ans, cur);
for(int i = 0; i < 2; ++i) {
int f = R + (i ? T : -T);
for(int k = (i ? t + 1 : M - t); k <= M; k += k&-k) {
auto j = s[i][k].insert({f, cur}).first;
if(next(j) != end(s[i][k]) && (*next(j))[1] <= cur)
s[i][k].erase(j);
else {
while(j != begin(s[i][k]) && (*prev(j))[1] >= cur)
s[i][k].erase(prev(j));
}
}
}
}
cout << (ans == INF ? -1 : ans);
}
