#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long inf=1e18;
long long ln,n,wg[100069],com[100069],nr[100069];
pair<long long,pair<long long,long long>> a[100069];
pair<long long,long long> xy[100069],as[100069];
priority_queue<pair<long long,long long>> pq;
struct segtree
{
long long l,r,nn;
vector<long long> vl,dsu;
segtree *p[2];
long long fd(long long x)
{
if(dsu[x]!=x)
{
dsu[x]=fd(dsu[x]);
}
return dsu[x];
}
void bd(long long lh,long long rh)
{
l=lh;
r=rh;
nn=0;
vl.push_back(0);
dsu.push_back(0);
if(l<r)
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
}
}
void ins(long long x,long long w)
{
if(l>x||r<x);
else
{
nn++;
vl.push_back(w);
dsu.push_back(nn);
if(!(l>=x&&r<=x))
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->ins(x,w);
}
}
}
}
void qr(long long lh,long long rh,long long ub,long long w)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
long long p;
for(;nn&&xy[vl[fd(1)]].sc<=ub;dsu[fd(1)]=fd((fd(1)+1)%(nn+1)))
{
p=vl[fd(1)];
if(w+wg[p]<nr[p])
{
pq.push({-w-wg[p],p});
nr[p]=w+wg[p];
}
}
}
else
{
long long ii;
for(ii=0;ii<2;ii++)
{
p[ii]->qr(lh,rh,ub,w);
}
}
}
}
sg;
int main()
{
long long i,k,l,w,ti,p,x,z=inf;
scanf("%lld%lld",&ln,&n);
xy[0]={inf,inf};
for(i=1;i<=n;i++)
{
scanf("%lld%lld%lld%lld",&ti,&k,&l,wg+i);
a[i]={ti,{k,l}};
xy[i]={k+ti,k-ti};
com[i]=k+ti;
as[i]={k-ti,i};
nr[i]=inf;
}
sort(com+1,com+n+1);
sort(as+1,as+n+1);
sg.bd(1,n);
for(i=1;i<=n;i++)
{
p=as[i].sc;
x=xy[p].fr;
sg.ins(lower_bound(com+1,com+n+1,x)-com,p);
}
for(i=1;i<=n;i++)
{
k=a[i].sc.fr;
if(k==1)
{
pq.push({-wg[i],i});
nr[i]=wg[i];
}
}
for(;!pq.empty();)
{
w=-pq.top().fr;
p=pq.top().sc;
pq.pop();
ti=a[p].fr;
l=a[p].sc.sc;
sg.qr(1,upper_bound(com+1,com+n+1,l+1+ti)-com-1,l+1-ti,w);
}
for(i=1;i<=n;i++)
{
l=a[i].sc.sc;
if(l==ln)
{
z=min(z,nr[i]);
}
}
if(z==inf)
{
z=-1;
}
printf("%lld\n",z);
}
