#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
struct segment
{
int t;
int l,r;
int cost;
segment(int _t, int _l, int _r, int _cost): t(_t), l(_l), r(_r), cost(_cost){}
bool operator < (const segment &s) const
{
if(t!=s.t) return t<s.t;
if(l!=s.l) return l<s.l;
if(r!=s.r) return r<s.r;
return cost<s.cost;
}
};
ll N; int n;
ll dist[333333];
vector<segment> vec;
vector<pair<int,int> > st[2][455555];
const ll INF = ll(1e18);
void add(int ty, int id, int l, int r, int pos, int nd)
{
if(pos>=r||pos<l) return ;
if(ty==0) st[ty][id].pb({vec[nd].l+vec[nd].t,nd});
else st[ty][id].pb({vec[nd].l-vec[nd].t,nd});
if(r-l<2) return ;
int mid=(l+r)>>1;
add(ty,id*2,l,mid,pos,nd); add(ty,id*2+1,mid,r,pos,nd);
}
void getnodes(int ty, int id, int l, int r, int ql, int qr, int X, vi &nodes) //<= X
{
if(ql>=r||l>=qr) return ;
if(ql<=l&&r<=qr)
{
while(!st[ty][id].empty()&&st[ty][id].back().fi<=X)
{
nodes.pb(st[ty][id].back().se);
st[ty][id].pop_back();
}
return ;
}
int mid=(l+r)>>1;
getnodes(ty,id*2,l,mid,ql,qr,X,nodes);
getnodes(ty,id*2+1,mid,r,ql,qr,X,nodes);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>N>>n;
vector<int> Tcoord;
for(int i=0;i<n;i++)
{
int t,l,r,c; cin>>t>>l>>r>>c; l--;
vec.pb(segment(t,l,r,c));
Tcoord.pb(t);
}
sort(Tcoord.begin(),Tcoord.end());
Tcoord.erase(unique(Tcoord.begin(),Tcoord.end()),Tcoord.end());
ll ans=ll(1e18);
for(int i=0;i<n;i++)
{
dist[i]=ll(1e18);
if(vec[i].l==0) continue;
add(0,1,0,Tcoord.size(),lower_bound(Tcoord.begin(),Tcoord.end(),vec[i].t)-Tcoord.begin(),i);
add(1,1,0,Tcoord.size(),lower_bound(Tcoord.begin(),Tcoord.end(),vec[i].t)-Tcoord.begin(),i);
}
for(int i=0;i<422222;i++)
{
for(int j=0;j<2;j++)
{
sort(st[j][i].rbegin(),st[j][i].rend());
}
}
priority_queue<ii,vector<ii>,greater<ii> > pq;
for(int i=0;i<n;i++)
{
if(vec[i].l==0)
{
pq.push({vec[i].cost,i});
dist[i]=vec[i].cost;
}
}
while(!pq.empty())
{
ii cur = pq.top(); pq.pop();
int u = cur.se; ll d = cur.fi;
int pos = lower_bound(Tcoord.begin(),Tcoord.end(),vec[u].t)-Tcoord.begin();
vector<int> nodes;
//T_j<T_i, search in st 1
getnodes(1,1,0,Tcoord.size(),0,pos,vec[u].r-vec[u].t,nodes);
//T_j>=T_i, search in st 0
getnodes(0,1,0,Tcoord.size(),pos,Tcoord.size(),vec[u].r+vec[u].t,nodes);
sort(nodes.begin(),nodes.end());
nodes.erase(unique(nodes.begin(),nodes.end()),nodes.end());
for(int x:nodes)
{
if(dist[x]>=INF)
{
dist[x]=min(dist[x],d+vec[x].cost);
pq.push({dist[x],x});
}
}
}
for(int i=0;i<n;i++)
{
if(vec[i].r==N)
{
ans=min(ans,dist[i]);
}
}
if(ans>=ll(1e17)) ans=-1;
cout<<ans<<'\n';
}
