#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;
using ll = long long;
const int N=1<<17;
const ll INF=1e18;
ll dist[N];
bool vis[N];
int main(){
int l, n;
cin>>l>>n;
vector<pair<pair<int, int>, pair<int, int>> > V(n);
for(int i=0; i<n; ++i){
cin>>V[i].nd.st>>V[i].st.st>>V[i].st.nd>>V[i].nd.nd;
V[i].st.st--;
}
for(int i=0; i<n; i++){
if(V[i].st.st)dist[i]=INF;
else dist[i]=V[i].nd.nd;
}
for(int ii=0; ii<n; ii++){
int opt=0;
for(int j=0; j<n; j++){
//cout<<dist[j]<<" \n"[j==n-1];
if(!vis[j] && (vis[opt] || dist[j]<dist[opt]))opt=j;
}
vis[opt]=1;
if(V[opt].st.nd==l && dist[opt]!=INF){
cout<<dist[opt];
return 0;
}
for(int i=0; i<n; i++){
if(V[i].st.st+V[i].nd.st<=V[opt].st.nd+V[opt].nd.st
&& V[i].st.st-V[i].nd.st<=V[opt].st.nd-V[opt].nd.st){
if(dist[i]>V[i].nd.nd+dist[opt]){
dist[i]=V[i].nd.nd+dist[opt];
}
}
}
}
cout<<-1;
}
