#include <bits/stdc++.h>
using namespace std;
#define int ll
#define ll long long
#define pii pair<ll, ll>
#define f first
#define s second
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define FOR(i,a,b) for (int i = a; i<b; ++i)
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<"- "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 3e5+5;
const int mod = 1e9+7;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct rect{
int x,y,r,c,i;
bool operator < (rect &R) {
if (x != R.x) return x < R.x;
return y < R.y;
}
};
bool isbeg[maxn], isend[maxn]; // for each rectangle, is it the beg or end?????
bool done[maxn];
ll dst[maxn];
pii s[maxn*4]; // minimum y position, index (in segment tree!!!!!)
void MO(int p, pii v, int o = 1, int l = 0, int r = maxn-1) {
if( l > p || r < p) return;
if( l == r) {
s[o] = v;
return;
}
int mid = (l+r)/2;
MO(p,v,o*2,l,mid); MO(p,v,o*2+1,mid+1,r);
s[o] = min(s[o*2],s[o*2+1]);
}
pii QU(int L, int R, int o=1, int l=0, int r=maxn-1) {
if (l > R || r < L) return {inf, -1};
if (l >= L && r <= R) return s[o];
int mid = (l+r)/2;
return min(QU(L,R,o*2,l,mid), QU(L,R,o*2+1,mid+1,r));
}
void build(){
fill(s, s+maxn*4, pii{inf,-1});
}
ll get(vector<rect> v) {
for (rect &R : v) {
bug(R.x,R.y,R.r,R.c,R.i);
bug(isbeg[R.i]);
bug(isend[R.i]);
}
// sort(ALL(v));
memset(dst, 0x3f, sizeof dst);
int n = SZ(v);
priority_queue<pii, vector<pii>, greater<pii> >pq;
vector<pair<pii, int> > pts;
build();
for (rect &R : v) {
if (isbeg[R.i]) {
dst[R.i]=R.c;
pq.push({dst[R.i], R.i});
}else{
pts.pb({{R.x, R.y}, R.i});
}
}
sort(ALL(pts));
for (rect &R : v) {
if (isbeg[R.i]) continue;
int meat = lower_bound(ALL(pts), make_pair(make_pair(R.x, R.y), R.i)) - pts.begin();
MO(meat, {R.y, meat});
}
ll re = inf;
while (!pq.empty()) {
int me = pq.top().s; ll w = pq.top().f; pq.pop();
if (dst[me] != w) continue;
if (isend[me]) {
MN(re, dst[me]);
}
pair<pii, int> moo = make_pair(make_pair(v[me].x + v[me].r + 1, v[me].y + v[me].r + 1), 1000000);
int upto = upper_bound(ALL(pts), moo) - pts.begin() - 1;
pii hi = QU(0,upto);
while (hi.s != -1) {
if (hi.f > v[me].y + v[me].r + 1) break;
// bug(hi.s);
int who = pts[hi.s].s;
bug(me, who);
dst[who] = v[who].c + dst[me];
pq.push({dst[who], who});
MO(hi.s, {inf, -1});
hi = QU(0, upto);
}
}
if (re == inf) return -1;
return re;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0);
bug(1,2);
vector<rect> go;
int n,m; cin>>n>>m;
REP(i,m) {
int t,l,r,c; cin>>t>>l>>r>>c;
--l; --r;
isbeg[i] = l == 0;
isend[i] = r == n-1;
go.pb({l+t, l-t,r-l,c,i});
}
ll re =get(go);
cout<<re<<endl;
}
/*
10 5
1 8 10 30
1 1 6 50
2 7 7 100
3 5 7 11
2 8 8 11
7 6 10 4
4 1 3 1
*/
