#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const int SZ=1<<18;
vector<pair<int,int>> tree[2*SZ];
vector<int> P, x, y;
vector<tuple<int,int,int,int,int>> A;
long long dist1[100000], dist2[100000];
int chk[100000];
void set_tree(int s, int e, int p, int i)
{
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) tree[s++].emplace_back(p,i);
if(~e&1) tree[e--].emplace_back(p,i);
}
}
void get_pos(int n, int l)
{
for(n+=SZ;n;n>>=1) while(tree[n].size() && l<=tree[n].back().first) {
P.push_back(tree[n].back().second);
tree[n].pop_back();
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M;
priority_queue<pair<long long,int>> Q;
long long ans=INF;
cin>>N>>M; A.resize(M);
memset(dist1,0x3f,sizeof(dist1));
memset(dist2,0x3f,sizeof(dist2));
for(int i=0;i<M;i++) {
auto &[t,l,r,aa,c]=A[i];
cin>>t>>l>>r>>c;
if(--l==0) chk[i]|=1;
if(r==N) chk[i]|=2;
x.push_back(l+t);
x.push_back(r+t);
y.push_back(l-t);
y.push_back(r-t);
tie(t,l,r,aa)=make_tuple(l+t,l-t,r+t,r-t);
}
sort(x.begin(),x.end()); x.resize(unique(x.begin(),x.end())-x.begin());
sort(y.begin(),y.end()); y.resize(unique(y.begin(),y.end())-y.begin());
for(int i=0;i<M;i++) {
auto &[x1,y1,x2,y2,c]=A[i];
x1=lower_bound(x.begin(),x.end(),x1)-x.begin();
y1=lower_bound(y.begin(),y.end(),y1)-y.begin();
x2=lower_bound(x.begin(),x.end(),x2)-x.begin();
y2=lower_bound(y.begin(),y.end(),y2)-y.begin();
if(chk[i]&1) Q.emplace(-(dist1[i]=c),i);
else set_tree(x1,x2,-y1,i);
}
for(int i=2*SZ;--i;) sort(tree[i].begin(),tree[i].end());
while(!Q.empty()) {
auto[t,c]=Q.top();
Q.pop();
P.clear();
auto[x1,y1,x2,y2,d]=A[c];
get_pos(x2,-y2);
for(auto n: P) if(dist1[n]==INF) {
auto[x1,y1,x2,y2,d]=A[n];
dist1[n]=dist1[c]+d;
Q.emplace(-dist1[n],n);
}
}
for(int i=2*SZ;--i;) tree[i].clear();
for(int i=0;i<M;i++) {
auto[x1,y1,x2,y2,c]=A[i];
if(chk[i]&2) Q.emplace(-(dist2[i]=c),i);
else set_tree(y1,y2,x2,i);
}
for(int i=2*SZ;--i;) sort(tree[i].begin(),tree[i].end());
while(!Q.empty()) {
auto[t,c]=Q.top();
Q.pop();
P.clear();
auto[x1,y1,x2,y2,d]=A[c];
get_pos(y1,x1);
for(auto n: P) if(dist2[n]==INF) {
auto[x1,y1,x2,y2,d]=A[n];
dist2[n]=dist2[c]+d;
Q.emplace(-dist2[n],n);
}
}
for(int i=0;i<M;i++) ans=min(ans,dist1[i]+dist2[i]-get<4>(A[i]));
cout<<(ans<INF ? ans:-1)<<'\n';
return 0;
}
