#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 8e5 + 10;
const int Mod = 998244353;

int read() {
    int x;
    scanf("%lld",&x);
    return x;
}

int n,m;
struct Interval {
    int tim,l,r,pay;
} a[N];

vector<int>G[N];
int dis[N];
bool vis[N];

inline void insert(int x,int y){
	G[x].push_back(y);
	printf("%d %d\n",x,y);
}

struct Segment_Tree {
    int maxn[N],minn[N];
    int ls[N],rs[N];
#define ls ls[pos]
#define rs rs[pos]
    int rt[2],tot;
    int leaf[2][N];//0 父连子 1 子连父
    void init(){
    	build(rt[0],1,n,0);
    	build(rt[1],1,n,1);
    	for(int i=1;i<=n;i++){
    		insert(leaf[0][i],leaf[1][i]);
		}
	}
    void build(int &pos,int l,int r,int flag) {
        pos=++tot;
        if(l==r) {
            maxn[pos]=a[l].l+a[l].tim;
            minn[pos]=a[l].r-a[l].tim;
            leaf[flag][l]=pos;
            return;
        }
        int mid=l+r>>1;
        build(ls,l,mid,flag);
        build(rs,mid+1,r,flag);
        maxn[pos]=max(maxn[ls],maxn[rs]);
        minn[pos]=min(minn[ls],minn[rs]);
        if(!flag) {
        	insert(pos,ls);
        	insert(pos,rs);
        } else {
        	insert(ls,pos);
        	insert(rs,pos);
        }
    }//如果编号qpos小于l 要求 r+tim>=l+tim
    //大于r 要求 l-tim-1<=r-tim
    void add(int pos,int l,int r,int qpos,int k,bool flag) { //flag0 qpos大于r flag1 qpos小于l
        if(!flag) {
            if(qpos<r) {
                int mid=l+r>>1;
                add(ls,l,mid,qpos,k,flag);
                if(mid<qpos) add(rs,mid+1,r,qpos,k,flag);
                return;
            }
			if(minn[pos]>=k){
				insert(pos,leaf[0][qpos]);
				return;
			}
			if(l==r) return;
            int mid=l+r>>1;
            add(ls,l,mid,qpos,k,flag);
            add(rs,mid+1,r,qpos,k,flag);
        } else{
        	if(qpos>l){
                int mid=l+r>>1;
                if(qpos<=mid) add(ls,l,mid,qpos,k,flag);
                add(rs,mid+1,r,qpos,k,flag);
                return;
			}
            if(maxn[pos]<=k) {
            	insert(leaf[0][qpos],pos);
                return;
            }
			if(l==r) return;
            int mid=l+r>>1;
            add(ls,l,mid,qpos,k,flag);
            add(rs,mid+1,r,qpos,k,flag);
        }
    }
}sgt;

void dijkstra() {
    memset(dis,0x3f,sizeof dis);
    priority_queue<pii,vector<pii>,greater<pii>>q;
    for(int i=1; i<=n; i++) {
        if(a[i].l==1) {
            dis[i]=a[i].pay;
            q.push({dis[i],sgt.leaf[1][i]});
        }
    }
    while(!q.empty()) {
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=true;
        for(int y:G[x]) {
            if(dis[y]>dis[x]+a[y].pay) {
                dis[y]=dis[x]+a[y].pay;
                q.push({dis[y],y});
            }
        }
    }
}

signed main() {
    m=read();
    n=read();
    for(int i=1; i<=n; i++) {
        int tim=read(),l=read(),r=read(),pay=read();
        a[i]= {tim,l,r,pay};
    }
    sort(a+1,a+n+1,[](Interval x,Interval y) {
        if(x.tim!=y.tim) return x.tim<y.tim;
        else if(x.l!=y.l) return x.l<y.l;
        else return x.r<y.r;
    });
    sgt.init();
    for(int i=1; i<=n; i++) {
        sgt.add(sgt.rt[0],1,n,i,a[i].l-a[i].tim-1,0);
        sgt.add(sgt.rt[1],1,n,i,a[i].r+a[i].tim,1);
    }
    dijkstra();
    int ans=inf;
    for(int i=1; i<=n; i++) {
        if(a[i].r==m) ans=min(ans,dis[sgt.leaf[1][i]]);
    }
    cout<<(ans==inf?-1:ans);
    return 0;
}