#include <vector>
#include <set>
#include <climits>
#include <iostream>
#define MAXN 2000005
using namespace std;
vector<pair<int,pair<int,int>>> graph[MAXN];
int mind[MAXN];
int esplora(int N){
    set<pair<int,int>> coda;
    coda.insert(make_pair(0,0));
    mind[0]=0;
    while(!coda.empty()){
        //cout<<"\nEHI";
        int where=coda.begin()->second;
        int time=coda.begin()->first;
        if(where==N-1) return time;
        coda.erase(coda.begin());
        for(auto ed:graph[where]){
            //cout<<" OK ";
            if(time<ed.second.second){
            ////cout<<"1 ";
                if(time>ed.second.first){
                  //cout<<mind[where]+1<<" ";
                    if(mind[ed.first]>mind[where]+1){
                        coda.erase({mind[ed.first],ed.first});
                        mind[ed.first]=mind[where]+1;
                        coda.insert({mind[ed.first],ed.first});
                    }
                }
                else{
                    //cout<<ed.second.first<<" ";
                    if(mind[ed.first]>ed.second.first+1){
                        ////cout<<"4 ";
                        coda.erase({mind[ed.first],ed.first});
                        mind[ed.first]=ed.second.first+1;
                        coda.insert({mind[ed.first],ed.first});
                    }
                }
            }
        }
    }
    //cout<<endl<<endl;
    return -1;
}


int raggiungi(int N, int M, int A[], int B[], int inizio[], int fine[]) {
    for(int i=0;i<N;i++){
        mind[i]=INT_MAX;
    }
    for(int i=0;i<M;i++){
        graph[A[i]].push_back(make_pair(B[i],make_pair(inizio[i],fine[i])));
        graph[B[i]].push_back(make_pair(A[i],make_pair(inizio[i],fine[i])));
    }
    return esplora(N);
}