#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll inf = 1e18;
struct SegTree {
ll base;
vector<pair<ll, ll>> T;
SegTree(ll n) {
base=1;
while(base <= n) base *= 2;
T.assign(2*base,{inf,0});
}
void set(ll x, ll val) {
x+=base;
T[x] = {val, x-base};
x/=2;
while(x > 0) {
T[x] = min(T[x+x], T[x+x+1]);
x/=2;
}
}
pair<ll, ll> query(ll a, ll b) {
if(a>b) return {inf,0};
if(a==b) return T[a+base];
a+=base-1;
b+=base+1;
pair<ll, ll> ans = {inf, 0};
while(a/2!=b/2) {
if(a%2==0) ans = min(ans, T[a+1]);
if(b%2==1) ans = min(ans, T[b-1]);
a/=2; b/=2;
}
return ans;
}
};
struct llerval {
ll t,l,r,c;
friend bool operator<(llerval a, llerval b) {
return a.t < b.t;
}
};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n, m;
cin >> n >> m;
vector<ll> T(m), L(m), R(m), C(m);
vector<llerval> is;
for(ll i=0; i<m; ++i) {
ll t,a,b,c;
cin >> t >> a >> b >> c;
is.push_back({t,a,b,c});
}
sort(is.begin(), is.end());
ll cnt = 0;
for(auto[t,a,b,c] : is) {
T[cnt] = t; L[cnt] = a-1;
R[cnt] = b; C[cnt] = c;
cnt++;
}
vector<ll> targets;
vector<ll> dist(m, inf);
auto check = [&](ll i, ll j) {
if(T[j] > T[i]) return (R[i] + T[i] >= L[j] + T[j]);
return (R[i] - T[i] >= L[j] - T[j]);
};
for(ll i=0; i<m; ++i) {
if(L[i]==0) dist[i] = C[i];
if(R[i]==n) targets.push_back(i);
}
SegTree tm(m),td(m);
for(ll i=0; i<m; ++i) {
tm.set(i,L[i]-T[i]);
td.set(i,L[i]+T[i]);
}
priority_queue<pair<ll, ll>> pq;
vector<ll> vis(m);
for(ll i=0; i<m; ++i) if(dist[i] < inf) pq.push({-dist[i], i});
while(pq.size()) {
auto[dv, v] = pq.top();
pq.pop(); dv*=-1;
if(vis[v]) continue;
vis[v] = 1;
vector<ll> verts;
if(v < m-1) {
auto[val,idx] = td.query(v+1,m-1);
while(val <= R[v] + T[v]) {
verts.push_back(idx);
td.set(idx, inf);
pair<ll, ll> para = td.query(v+1,m-1);
val = para.first; idx = para.second;
}
}
if(v > 0) {
auto[val,idx] = tm.query(0,v-1);
while(val <= R[v] - T[v]) {
verts.push_back(idx);
tm.set(idx, inf);
pair<ll, ll> para = tm.query(0,v-1);
val = para.first; idx = para.second;
}
}
for(auto u : verts) {
if(dist[u] > dist[v] + C[u]) {
dist[u] = dist[v] + C[u];
pq.push({-dist[u], u});
}
}
}
ll ans = inf;
for(ll x : targets) {
ans = min(ans, dist[x]);
}
if(ans==inf) cout << "-1\n";
else cout << ans << "\n";
return 0;
}
