#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
int s,e,m;
set<ii> v;
node *l,*r;
node (int _s,int _e){
s=_s,e=_e,m=s+e>>1;
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void ins(int i,ii j){
v.insert(j);
if (s==e) return;
if (i<=m) l->ins(i,j);
else r->ins(i,j);
}
void rem(int i,ii j){
v.erase(j);
if (s==e) return;
if (i<=m) l->rem(i,j);
else r->rem(i,j);
}
int query(int i,int j,int k){
if (s==i && e==j){
if (v.empty()) return -1;
if ((*v.begin()).fi<=k) return (*v.begin()).se;
else return -1;
}
else if (j<=m) return l->query(i,j,k);
else if (m<i) return r->query(i,j,k);
else{
int temp=l->query(i,m,k);
if (temp==-1) return r->query(m+1,j,k);
else return temp;
}
}
} *root1=new node(0,100005),*root2=new node(0,100005);
int n,k;
struct E{
int l,r;
int t;
ll cost;
int dt; //discretized time
};
vector<E> v;
struct upd{
int segno; //which tree
int i,j,k;
ll val;
};
struct cmp{
bool operator () (upd i,upd j){
return i.val>j.val;
}
};
priority_queue<upd,vector<upd>,cmp> pq;
int main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>k;
int a,b,c,d;
rep(x,0,k){
cin>>a>>b>>c>>d;
v.pub({b,c+1,a,d});
}
vector<int> allt;
rep(x,0,k) allt.pub(v[x].t);
sort(all(allt));
allt.erase(unique(all(allt)),allt.end());
map<int,int> tid;
rep(x,0,sz(allt)) tid[allt[x]]=x+1;
rep(x,0,k) v[x].dt=tid[v[x].t];
ll ans=1e18;
rep(x,0,k){
if (v[x].l==1){
if (v[x].r==n+1) ans=min(ans,v[x].cost);
pq.push(upd({1,v[x].dt,100005,v[x].r+v[x].t,v[x].cost}));
pq.push(upd({2,0,v[x].dt-1,v[x].r-v[x].t,v[x].cost}));
}
else{
root1->ins(v[x].dt,ii(v[x].l+v[x].t,x));
root2->ins(v[x].dt,ii(v[x].l-v[x].t,x));
}
}
while (!pq.empty()){
upd u=pq.top();
pq.pop();
if (u.segno==1){
while (true){
int x=root1->query(u.i,u.j,u.k);
if (x==-1) break;
pq.push(upd({1,v[x].dt,100005,v[x].r+v[x].t,v[x].cost+u.val}));
pq.push(upd({2,0,v[x].dt-1,v[x].r-v[x].t,v[x].cost+u.val}));
root1->rem(v[x].dt,ii(v[x].l+v[x].t,x));
root2->rem(v[x].dt,ii(v[x].l-v[x].t,x));
if (v[x].r==n+1) ans=min(ans,v[x].cost+u.val);
}
}
else{
while (true){
int x=root2->query(u.i,u.j,u.k);
if (x==-1) break;
pq.push(upd({1,v[x].dt,100005,v[x].r+v[x].t,v[x].cost+u.val}));
pq.push(upd({2,0,v[x].dt-1,v[x].r-v[x].t,v[x].cost+u.val}));
root1->rem(v[x].dt,ii(v[x].l+v[x].t,x));
root2->rem(v[x].dt,ii(v[x].l-v[x].t,x));
if (v[x].r==n+1) ans=min(ans,v[x].cost+u.val);
}
}
}
if (ans==1e18) cout<<"-1"<<endl;
else cout<<ans<<endl;
}
