#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;
const int inf=1e18;
struct ST{
vector<set<pair<int,int> > > st;
void init(int x){
st.resize(4*x);
}
void update(int v,int L,int R,int p,pair<int,int> k,int t){
if(t>0){
st[v].insert(k);
}
else{
st[v].erase(st[v].find(k));
}
if(L==R){
return;
}
int m=(L+R)/2;
if(p<=m){
update(2*v+1,L,m,p,k,t);
}
else{
update(2*v+2,m+1,R,p,k,t);
}
}
pair<int,int> query(int v,int L,int R,int p){
if(L==R){
if(st[v].size()){
return *st[v].begin();
}
else{
return {inf,-1};
}
}
int m=(L+R)/2;
if(p<=m){
return query(2*v+1,L,m,p);
}
else{
pair<int,int> a,b=query(2*v+2,m+1,R,p);
if(st[2*v+1].size()){
a=*st[2*v+1].begin();
}
else{
a={inf,-1};
}
return min(a,b);
}
}
}st;
signed main(){
AquA;
int n,m;
cin >> m >> n;
vector<int> cx(n),px,py,a(n),b(n);
vector<pair<int,int> > vl(n),vr(n);
for(int i=0;i<n;i++){
int l,r,t,c;
cin >> t >> l >> r >> c;
a[i]=l;
b[i]=r;
vl[i]={l-t,l+t};
vr[i]={r-t+1,r+t+1};
px.push_back(vl[i].fs);
px.push_back(vr[i].fs);
py.push_back(vl[i].sc);
py.push_back(vr[i].sc);
// vl[l] to node <= vr[r]
cx[i]=c;
}
sort(px.begin(),px.end());
sort(py.begin(),py.end());
px.erase(unique(px.begin(),px.end()),px.end());
py.erase(unique(py.begin(),py.end()),py.end());
int s=px.size();
st.init(s);
for(int i=0;i<n;i++){
vl[i].fs=lower_bound(px.begin(),px.end(),vl[i].fs)-px.begin();
vr[i].fs=lower_bound(px.begin(),px.end(),vr[i].fs)-px.begin();
vl[i].sc=lower_bound(py.begin(),py.end(),vl[i].sc)-py.begin();
vr[i].sc=lower_bound(py.begin(),py.end(),vr[i].sc)-py.begin();
st.update(0,0,s-1,vl[i].fs,{vl[i].sc,i},1);
}
int ans=1e18;
p_q<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
for(int i=0;i<n;i++){
if(a[i]==1){
pq.push({cx[i],i});
st.update(0,0,s-1,vl[i].fs,{vl[i].sc,i},-1);
}
}
while(pq.size()){
auto h=pq.top();
//cout << h.fs << " " << h.sc << "\n";
pq.pop();
if(b[h.sc]==m){
ans=min(ans,h.fs);
}
while(1){
auto y=st.query(0,0,s-1,vr[h.sc].fs);
if(y.sc==-1 || y.fs>vr[h.sc].sc){
break;
}
st.update(0,0,s-1,vl[y.sc].fs,{vl[y.sc].sc,y.sc},-1);
pq.push({h.fs+cx[y.sc],y.sc});
}
}
if(ans>5e17){
cout << -1 << "\n";
}
else{
cout << ans << "\n";
}
return 0;
}
