#include <iostream>
#include <queue>
using namespace std;
queue<pair<int,int>> q1;
const int MAXN = 2010;
vector<int> v1[MAXN];
bool visited[MAXN];
int dp[MAXN][MAXN];
bool visited2[MAXN][MAXN];
int first,jump;
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
int b,p;
cin>>b>>p;
if(i== 0){
first = b;
jump = p;
}
cin>>b>>p;
v1[b].push_back(p);
}
q1.push(make_pair(first,jump));
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
dp[i][j]= 1e9;
}
}
dp[first][jump] = 0;
while(!q1.empty()){
auto hold = q1.front();
int skyscraper = hold.first;
int hop = hold.second;
q1.pop();
if(skyscraper == 1){
cout<<dp[skyscraper][hop]<<endl;
return 0;
}
if(visited2[skyscraper][hop]){
continue;
}
// cout<<dp[skyscraper][hop]<<" "<<skyscraper<<" "<<hop<<" "<<endl;
visited2[skyscraper][hop] = true;
if(skyscraper-hop>=0){
if(dp[skyscraper-hop][hop]>=dp[skyscraper][hop]+1){
dp[skyscraper-hop][hop] = dp[skyscraper][hop]+1;
q1.push(make_pair(skyscraper-hop,hop));
}
}
if(skyscraper+hop<=n){
if(dp[skyscraper+hop][hop]>=dp[skyscraper][hop]+1){
dp[skyscraper+hop][hop] = dp[skyscraper][hop]+1;
q1.push(make_pair(skyscraper+hop,hop));
}
}
if(!visited[skyscraper]){
visited[skyscraper] =true;
for(int x:v1[skyscraper]){
if(x!=hop){
if(skyscraper-x>=0){
if(dp[skyscraper-x][x]>=dp[skyscraper][hop]+1){
dp[skyscraper-x][x] = dp[skyscraper][hop]+1;
q1.push(make_pair(skyscraper-x,x));
}
}
if(skyscraper+x<=n){
if(dp[skyscraper+x][x]>=dp[skyscraper][hop]+1){
dp[skyscraper+x][x] = dp[skyscraper][hop]+1;
q1.push(make_pair(skyscraper+x,x));
}
}
}
}
}
}
cout<<-1<<endl;
}
