#include <bits/stdc++.h>
using namespace std;
const int nx=5e3+5;
#define ll long long
struct plan
{
ll l, r, t, c;
} p[nx];
ll n, m, dpl[nx], dpr[nx], res=1e18;
vector<pair<ll, ll>> v;
bool isect(int x, int y)
{
return ((p[x].r+p[x].t)-(p[y].l-p[y].t)+1)/2>=max(p[x].t, p[y].t);
}
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>m;
for (int i=1; i<=m; i++) cin>>p[i].t>>p[i].l>>p[i].r>>p[i].c, dpl[i]=dpr[i]=1e18;
for (int i=1; i<=m; i++) v.push_back({p[i].r+p[i].t, i});
sort(v.begin(), v.end());
for (int i=0; i<m; i++)
{
int idx=v[i].second;
if (p[idx].l==1) dpl[idx]=p[idx].c;
else for (int j=0; j<i; j++) if (isect(v[j].second, idx)) dpl[idx]=min(dpl[idx], dpl[v[j].second]+p[idx].c);
}
v.clear();
for (int i=1; i<=m; i++) v.push_back({p[i].l-p[i].t, i});
sort(v.begin(), v.end());
for (int i=m-1; i>=0; i--)
{
int idx=v[i].second;
if (p[idx].r==n) dpr[idx]=p[idx].c;
else for (int j=i+1; j<m; j++) if (isect(idx, v[j].second)) dpr[idx]=min(dpr[idx], dpr[v[j].second]+p[idx].c);
}
//cout<<"debug "<<dpl[1]<<' '<<dpr[1]<<'\n';
for (int i=1; i<=m; i++) for (int j=1; j<=m; j++) if (isect(i, j)) res=min(res, dpl[i]+dpr[j]);
for (int i=1; i<=m; i++) if (p[i].l==1&&p[i].r==n) res=min(res, p[i].c);
if (res!=1e18) cout<<res;
else cout<<-1;
}
/*
10 2
1 1 6 1
2 7 10 1
*/
