#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push back
#define pii pair<int, int>
#define pll pair<ll, int>
using namespace std;
const int N = 1e6 + 6;
const int mod = 1e9 + 7;
const int inf = 2e9 + 7;
struct node
{
int t, l, r, v;
bool operator<(const node &u) const
{
return t < u.t;
}
} d[N];
struct IT
{
int n;
vector<pii> st;
IT(int _n)
{
n = _n;
st.resize(n * 4 + 4, make_pair(inf, 0));
}
void build(int id, int l, int r, int pos, pii v)
{
if (l == r)
{
st[id] = v;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid)
build(id << 1, l, mid, pos, v);
else
build(id << 1 | 1, mid + 1, r, pos, v);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void build(int pos, pii v)
{
build(1, 1, n, pos, v);
}
pii get(int id, int l, int r, int u, int v)
{
if (u <= l && r <= v)
return st[id];
if (u > r || l > v)
return make_pair(inf, 0);
int mid = (l + r) >> 1;
return min(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
pii get(int l, int r)
{
if (l > r)
return make_pair(inf, 0);
return get(1, 1, n, l, r);
}
};
int n, m, k, t, a[N], b[N], l[N], r[N];
ll ans;
int main()
{
cin.tie(0);
cin >> n >> m;
ans = -1;
priority_queue<pll, vector<pll>, greater<pll>> pq;
for (int i = 1; i <= m; i++)
cin >> d[i].t >> d[i].l >> d[i].r >> d[i].v;
sort(d + 1, d + 1 + m);
IT L(m), R(m);
for (int i = 1; i <= m; i++)
{
--d[i].l;
//cout << d[i].t << " " << d[i].l << " " << d[i].r << " " << d[i].v << '\n';
if (i > 1 && d[i].t == d[i - 1].t)
l[i] = l[i - 1];
else
l[i] = i;
if (d[i].l == 0)
{
pq.push({d[i].v, i});
continue;
}
L.build(i, make_pair(d[i].l - d[i].t, i));
R.build(i, make_pair(d[i].l + d[i].t, i));
}
r[m] = m;
for (int i = m - 1; i > 0; i--)
{
if (d[i].t == d[i + 1].t)
r[i] = r[i + 1];
else
r[i] = i;
}
while (!pq.empty())
{
pll u = pq.top();
pq.pop();
//cout << u.se << " " << u.fi << '\n';
if (d[u.se].r == n)
{
if (ans == -1 || ans > u.fi)
ans = u.fi;
}
k = d[u.se].r - d[u.se].t;
while (true)
{
pii v = L.get(1, r[u.se]);
if (v.fi <= k)
{
L.build(v.se, make_pair(inf, 0));
R.build(v.se, make_pair(inf, 0));
pq.push({u.fi+d[v.se].v, v.se});
}
else
break;
}
k = d[u.se].r + d[u.se].t;
while (true)
{
pii v = R.get(l[u.se], m);
if (v.fi <= k)
{
R.build(v.se, make_pair(inf, 0));
L.build(v.se, make_pair(inf, 0));
pq.push({u.fi+d[v.se].v, v.se});
}
else
break;
}
}
cout << ans;
}
