#include <set>
#include <map>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x;
}

int main() { 
    int n = rd();
    int m = rd();
    map<int, vector<int> > a;
    for (int i = 1; i <= m; ++i) a[rd()].push_back(rd());
    set<int> f{n};
    for (auto v : a) {
        vector<int> add, del;
        for (auto y : v.second) 
            if (f.count(y - 1) || f.count(y + 1)) add.push_back(y);
            else del.push_back(y);
        for (auto y : add) f.insert(y);
        for (auto y : del) f.erase(y);
    }
    printf("%d\n", f.size());
    return 0;
}
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;

/* [💭] [💡] [🎈] */

const ll inf = 1e18;
using pll = pair<ll, ll>;

ll dist[100001];

struct edge {
    int to;
    ll c, d;

    edge() : to(0), c(0), d(0) {}

    edge(int to, ll c, ll d) : to(to), c(c), d(d) {}
};

ll f(ll t, ll c, ll d) {
    return t + c + d / (t + 1);
}

ll mnt(ll dt, ll c, ll d) {
    ll mn = inf;
    ld ta = max(dt, (ll) sqrt(d) - 1);
    for (ll x = ta; x <= ta + 10; x++) {
        mn = min(mn, f(x, c, d));
    }
    return mn;
}

int main() {
    cin.tie(nullptr), cout.tie(nullptr), ios::sync_with_stdio(false);

#ifdef _SHIFTPSH
    freopen("_run/in.txt", "r", stdin), freopen("_run/out.txt", "w", stdout);
#endif

    fill(dist, dist + 100001, inf);

    int n, m;
    cin >> n >> m;

    vector<vector<edge>> graph(n + 1);
    while (m--) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        graph[u].emplace_back(v, c, d);
        graph[v].emplace_back(u, c, d);
    }

    dist[1] = 0;
    priority_queue<pll> pq;
    pq.emplace(0, 1);
    while (pq.size()) {
        ll c = -pq.top().first, u = pq.top().second;
        pq.pop();
        if (dist[u] < c) continue;

        for (const auto &e : graph[u]) {
            ll d = mnt(c, e.c, e.d);
            if (dist[e.to] <= d) continue;
            dist[e.to] = d;
            pq.emplace(-d, e.to);
        }
    }

    cout << (dist[n] == inf ? -1ll : dist[n]);

    return 0;
}