#include <vector>
#include <algorithm>
#include <limits>
#include <queue>

using namespace std;

const int oo = numeric_limits<int>::max();

struct step {
    int curr, dist;

    step() {}
    step(int c, int d):curr(c), dist(d){}

    bool operator<(const step& s)
        const {
        return dist>s.dist;
    }
};

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
vector<vector<iii>> graph;

vector<int> dist;

int raggiungi(int N, int M, int A[], int B[], int in[], int fine[]) {
    graph.resize(N);
    for (int i = 0; i < M; i++) {
        ii temp = ii(in[i], fine[i]);
        graph[A[i]].push_back({ B[i], temp });
        graph[B[i]].push_back({ A[i], temp });
    }
    dist.assign(N, oo);
    dist[0] = 0;
    priority_queue<step> Q;
    Q.push({ 0, 0 });
    while (!Q.empty()) {
        step head = Q.top(); Q.pop();
        if (dist[head.curr] == oo) {
            dist[head.curr] = head.dist;

            if (head.curr == N - 1)
                return dist[head.curr];

            for (auto i : graph[head.curr])
                if (i.second.second > head.dist)
                    if (max(i.second.first, dist[head.curr] + 1) < dist[i.first])
                        Q.push(step(i.first, max(i.second.first, dist[head.curr] + 1)));
        }
    }

    return (dist[N - 1] == oo) ? -1 : dist[N - 1];
}