#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; }