#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mmax=1e5+5;
struct tratament
{
int t,l,r,c;
};
tratament trat[Mmax];
bool viz[Mmax];
map<int,int> nrm;
vector<pair<int,int>> g[Mmax];
set<pair<int,int>> aint[4*Mmax][5];
vector<int> intime[Mmax];
void build(int nod,int l,int r)
{
if(l==r)
{
for(int idx:intime[l])
{
aint[nod][1].insert({trat[idx].l+trat[idx].t-1,idx});
aint[nod][2].insert({trat[idx].l-trat[idx].t-1,idx});
}
return;
}
int mid=(l+r)/2;
build(2*nod,l,mid);
build(2*nod+1,mid+1,r);
for(auto x:aint[2*nod][1]) aint[nod][1].insert(x);
for(auto x:aint[2*nod][2]) aint[nod][2].insert(x);
for(auto x:aint[2*nod+1][1]) aint[nod][1].insert(x);
for(auto x:aint[2*nod+1][2]) aint[nod][2].insert(x);
return;
}
vector<int> query(int nod,int l,int r,int st,int dr,int cmp,int tip)
{
if(st<=l && r<=dr)
{
vector<pair<int,int>> er;
vector<int> ans;
for(auto pi:aint[nod][tip])
{
if(viz[pi.second])
{
er.push_back(pi);
continue;
}
if(pi.first>cmp) break;
er.push_back(pi);
ans.push_back(pi.second);
}
for(auto x:er)
{
aint[nod][tip].erase(x);
}
return ans;
}
int mid=(l+r)/2;
if(dr<=mid) return query(2*nod,l,mid,st,dr,cmp,tip);
else if(mid<st) return query(2*nod+1,mid+1,r,st,dr,cmp,tip);
else
{
vector<int> vst=query(2*nod,l,mid,st,mid,cmp,tip);
vector<int> vdr=query(2*nod+1,mid+1,r,mid+1,dr,cmp,tip);
if(vst.size()>vdr.size())
{
for(int x:vdr) vst.push_back(x);
return vst;
}
for(int x:vst) vdr.push_back(x);
return vdr;
}
}
signed main()
{
int n,m;
cin>>n>>m;
priority_queue<pair<int,int>> pq;
bool ok=1;
for(int i=1;i<=m;i++)
{
cin>>trat[i].t>>trat[i].l>>trat[i].r>>trat[i].c;
nrm[trat[i].t]=0;
if(trat[i].t!=1) ok=0;
if(trat[i].l==1)
{
pq.push({-trat[i].c,i});
viz[i]=1;
}
}
int cnt=1;
for(auto [timp,v]:nrm)
{
nrm[timp]=cnt;
cnt++;
}
cnt--;
for(int i=1;i<=m;i++)
{
intime[nrm[trat[i].t]].push_back(i);
}
build(1,1,cnt);
/*
for(int i=1;i<=m;i++)
{
for(int j=1;j<=m;j++)
{
if(j==i) continue;
if(trat[i].t<trat[j].t)
{
if(trat[i].r+trat[i].t>=trat[j].l+trat[j].t-1) g[i].push_back({j,trat[j].c});
}
else
{
if(trat[i].r-trat[i].t>=trat[j].l-trat[j].t-1) g[i].push_back({j,trat[j].c});
}
}
}*/
while(!pq.empty())
{
auto [val,nod]=pq.top();
pq.pop();
if(trat[nod].r==n)
{
cout<<-val<<'\n';
return 0;
}
vector<int> nxtnodes1;
if(nrm[trat[nod].t]+1<=cnt) nxtnodes1=query(1,1,cnt,nrm[trat[nod].t]+1,cnt,trat[nod].r+trat[nod].t,1);
vector<int> nxtnodes2=query(1,1,cnt,1,nrm[trat[nod].t],trat[nod].r-trat[nod].t,2);
for(int u:nxtnodes1)
{
pq.push({val-trat[u].c,u});
viz[u]=1;
}
for(int u:nxtnodes2)
{
pq.push({val-trat[u].c,u});
viz[u]=1;
}
}
cout<<-1<<'\n';
return 0;
}
