#include <bits/stdc++.h>
using namespace std;
pair<pair<int,int>,pair<int,int> > arr[100005];
pair<int,int> ran[100005];
struct node{
int s,e,m;
node *l, *r;
int val;
node(int S, int E){
s=S; e=E;
if(s+e>=0) m=(s+e)/2;
else m=(s+e-1)/2;
val=100004;
l=r=NULL;
}
void prop(){
if(l==NULL){
l=new node(s,m);
r=new node(m+1,e);
}
}
void update(int S, int V){
if(s==e){
val=V;
return;
}
prop();
if(S<=m) l->update(S,V);
else r->update(S,V);
val=(ran[l->val].second<=ran[r->val].second?l->val:r->val);
}
int query(int S, int E){
if(S<=s&&e<=E) return val;
if(l==NULL) return 100004;
if(E<=m) return l->query(S,E);
else if(S>m) return r->query(S,E);
else{
int a=l->query(S,m),b=r->query(m+1,E);
return (ran[a].second<=ran[b].second?a:b);
}
}
} *root;
bool cmp(int a, int b){
return ran[a].second>ran[b].second;
}
unordered_map<int,vector<int> > um;
priority_queue<pair<long long,int>,vector<pair<long long,int> >,greater<pair<long long,int> > > pq;
int32_t main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ran[100004]={2e9+5,2e9+5};
int n,m;
root=new node(-2e9-5,2e9+5);
cin >> n >> m;
for(int i=0; i<m; i++){
int t,l,r,c;
cin >> t >> l >> r >> c;
arr[i]={{t,l},{r,c}};
ran[i]={t-l,t+l};
if(l==1){
pq.push({c,i});
}
else um[t-l].push_back(i);
}
for(auto [i,j]:um){
sort(um[i].begin(),um[i].end(),cmp);
root->update(i,um[i].back());
um[i].pop_back();
}
while(!pq.empty()){
long long a=pq.top().first;
int b=pq.top().second;
pq.pop();
if(arr[b].second.first==n){
cout << a;
return 0;
}
pair<int,int> qu={arr[b].first.first-arr[b].second.first-1,arr[b].first.first+arr[b].second.first+1};
while(true){
int x=root->query(qu.first,qu.second);
if(x==100004||ran[x].second>qu.second) break;
pq.push({a+arr[x].second.second,x});
if(!um[ran[x].first].empty()){
root->update(ran[x].first,um[ran[x].first].back());
um[ran[x].first].pop_back();
}
else root->update(ran[x].first,100004);
}
}
cout << -1;
return 0;
}
