#include <bits/stdc++.h>
using namespace std;
const int N = 4e5;
const int M = 4 * N;
set<pair<int, int>> all[2][N];
struct node {
pair<int, int> mn;
pair<int, int> mx;
} st[2][M];
node comb(node a, node b) {
node res;
res.mn = min(a.mn, b.mn);
res.mx = max(a.mx, b.mx);
return res;
}
void Build(int t, int x, int l, int r) {
st[t][x].mn = {1.00001e9, -1};
st[t][x].mx = {-1.00001e9, -1};
if (l == r) {
return;
}
int mid = l + r >> 1;
Build(t, x * 2, l, mid);
Build(t, x * 2 + 1, mid + 1, r);
}
void Modify(int t, int x, int l, int r, int p, pair<int, int> v) {
if (l == r) {
all[t][l].insert(v);
st[t][x].mn = *all[t][l].begin();
st[t][x].mx = *prev(all[t][l].end());
return;
}
int mid = l + r >> 1;
if (p <= mid) {
Modify(t, x * 2, l, mid, p, v);
} else {
Modify(t, x * 2 + 1, mid + 1, r, p, v);
}
st[t][x] = comb(st[t][x * 2], st[t][x * 2 + 1]);
}
void Remove(int t, int x, int l, int r, int p, pair<int, int> v) {
if (l == r) {
all[t][l].erase(all[t][l].find(v));
if (all[t][l].empty()) {
st[t][x].mn = {1.00001e9, -1};
st[t][x].mx = {-1.00001e9, -1};
} else {
st[t][x].mn = *all[t][l].begin();
st[t][x].mx = *prev(all[t][l].end());
}
return;
}
int mid = l + r >> 1;
if (p <= mid) {
Remove(t, x * 2, l, mid, p, v);
} else {
Remove(t, x * 2 + 1, mid + 1, r, p, v);
}
st[t][x] = comb(st[t][x * 2], st[t][x * 2 + 1]);
}
node Query(int t, int x, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return st[t][x];
}
int mid = l + r >> 1;
if (qr <= mid) {
return Query(t, x * 2, l, mid, ql, qr);
} else if (ql > mid) {
return Query(t, x * 2 + 1, mid + 1, r, ql, qr);
} else {
return comb(Query(t, x * 2, l, mid, ql, qr), Query(t, x * 2 + 1, mid + 1, r, ql, qr));
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> t(m), l(m), r(m), c(m);
for (int i = 0; i < m; i++) {
cin >> t[i] >> l[i] >> r[i] >> c[i];
--l[i];
}
vector<int> xs;
for (int i = 0; i < m; i++) {
xs.push_back(l[i] - t[i]);
xs.push_back(l[i] + t[i]);
xs.push_back(r[i] - t[i]);
xs.push_back(r[i] + t[i]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
auto GetVal = [&](int x) {
return (int) (lower_bound(xs.begin(), xs.end(), x) - xs.begin());
};
int k = (int) xs.size();
Build(0, 1, 0, k - 1);
Build(1, 1, 0, k - 1);
for (int i = 0; i < m; i++) {
Modify(0, 1, 0, k - 1, GetVal(l[i] - t[i]), {t[i], i});
Modify(1, 1, 0, k - 1, GetVal(l[i] + t[i]), {t[i], i});
}
const long long inf = (long long) 1e18;
vector<long long> dist(m, inf);
set<pair<long long, int>> st;
for (int i = 0; i < m; i++) {
if (l[i] == 0) {
dist[i] = c[i];
st.emplace(dist[i], i);
Remove(0, 1, 0, k - 1, GetVal(l[i] - t[i]), {t[i], i});
Remove(1, 1, 0, k - 1, GetVal(l[i] + t[i]), {t[i], i});
}
}
while (!st.empty()) {
auto it = st.begin();
int i = it->second;
st.erase(it);
while (true) {
{
node nd = Query(0, 1, 0, k - 1, 0, GetVal(r[i] - t[i]));
if (nd.mn.first <= t[i]) {
int j = nd.mn.second;
dist[j] = dist[i] + c[j];
Remove(0, 1, 0, k - 1, GetVal(l[j] - t[j]), {t[j], j});
Remove(1, 1, 0, k - 1, GetVal(l[j] + t[j]), {t[j], j});
st.emplace(dist[j], j);
continue;
}
}
{
node nd = Query(1, 1, 0, k - 1, 0, GetVal(r[i] + t[i]));
if (nd.mx.first >= t[i]) {
int j = nd.mx.second;
dist[j] = dist[i] + c[j];
Remove(0, 1, 0, k - 1, GetVal(l[j] - t[j]), {t[j], j});
Remove(1, 1, 0, k - 1, GetVal(l[j] + t[j]), {t[j], j});
st.emplace(dist[j], j);
continue;
}
}
break;
}
}
long long res = inf;
for (int i = 0; i < m; i++) {
if (r[i] == n) {
res = min(res, dist[i]);
}
}
cout << (res == inf ? -1 : res) << '\n';
return 0;
}
