#include <iostream>
#include <vector>
#include <algorithm>
#define int ll
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define ff first
#define ss second
const int MAXM = 1e5 + 7;
ll dp[MAXM];
int n;
bool inter(int a, int b, int d, int a2, int b2, int d2) {
int r = abs(d - d2);
if (d > d2) {
swap(a, a2);
swap(b, b2);
swap(d, d2);
}
if (b != n) {
b -= r;
}
if (a != 1) a += r;
if (b > b2) {
swap(b, b2);
swap(a, a2);
}
//cout << "K2: " << a << ' ' << b << ' ' << a2 << ' ' << b2 << '\n';
return (b + 1) >= a2;
}
bool comp(pair<pii, pii> a, pair<pii, pii> b) {
if (a.first.ss == n) return 0;
if (b.first.ss == n) return 1;
return a.first.ss + a.second.first < b.ff.ss + b.ss.ff;
}
bool comp2(pair<pii, pii> a, pair<pii, pii> b) {
if (a.ff.ff == 1) return 0;
if (b.ff.ff == 1) return 1;
return a.first.first - a.second.first > b.ff.ff - b.ss.ff;
}
//a - t > a2 - t2
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int m, a, b, c, d;
cin >> n >> m;
vector<pair<pii, pii>> tab;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c >> d;
tab.push_back({{b, c}, {a, d}});
}
sort(tab.begin(), tab.end(), comp);
ll ans = 1e18;
for (int i = 0; i < m; i++) {
int l = tab[i].ff.ff;
int r = tab[i].ff.ss;
int t = tab[i].ss.ff;
int c = tab[i].ss.ss;
dp[i] = 1e18;
if (l == 1) {
dp[i] = c;
if (r == n) ans = min(ans, dp[i]);
//cout << l << ' ' << r << ' ' << t << ' ' << c << ' ' << dp[i] << '\n';
continue;
}
for (int j = 0; j < i; j++) {
if (inter(l, r, t, 1, tab[j].ff.ss, tab[j].ss.ff)) {
dp[i] = min(dp[i], dp[j] + c);
//cout << "OH: " << l << ' ' << r << ' ' << t << ' ' << c << ": " << tab[j].ff.ss << ' ' << tab[j].ff.ff << ' ' << tab[j].ss.ff << ' ' << dp[j] + c << '\n';
}
}
//cout << l << ' ' << r << ' ' << t << ' ' << c << ' ' << dp[i] << '\n';
if (r == n) ans = min(ans, dp[i]);
}
sort(tab.begin(), tab.end(), comp2);
for (int i = 0; i < m; i++) {
int l = tab[i].ff.ff;
int r = tab[i].ff.ss;
int t = tab[i].ss.ff;
int c = tab[i].ss.ss;
dp[i] = 1e18;
if (r == n) {
dp[i] = c;
if (l == 1) ans = min(ans, dp[i]);
//cout << l << ' ' << r << ' ' << t << ' ' << c << ' ' << dp[i] << '\n';
continue;
}
for (int j = 0; j < i; j++) {
if (inter(l, r, t, tab[j].ff.ff, n, tab[j].ss.ff)) {
dp[i] = min(dp[i], dp[j] + c);
//cout << "OH: " << l << ' ' << r << ' ' << t << ' ' << c << ": " << tab[j].ff.ss << ' ' << tab[j].ff.ff << ' ' << tab[j].ss.ff << ' ' << dp[j] + c << '\n';
}
}
// cout << l << ' ' << r << ' ' << t << ' ' << c << ' ' << dp[i] << '\n';
if (l == 1) ans = min(ans, dp[i]);
}
if (ans == 1e18) ans = -1;
cout << ans << '\n';
return 0;
}
