#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

struct edge {
    int to;
    long long c;
    long long d;
};

ll get_cost(ll c, ll d, ll t_now) {
    ll t = sqrt(d);
    ll dt = max(0LL, t - t_now);
    ll res = c + (d / (t_now + dt + 1)) + dt;
    res = min(res, c + (d / (t_now + dt + 1 + 1)) + dt + 1);
    if (dt) res = min(res, c + (d / (t_now + dt - 1 + 1)) + dt - 1);
    return res;
}

const long long INF = 10e16;

// 0-indexed
vector<long long> dijkstra(int start, vector<vector<edge>> &G) {
    int N = G.size();

    vector<long long> dist(N, INF);
    priority_queue<P, vector<P>, greater<P>> pq;

    dist.at(start) = 0;
    pq.emplace(P{dist.at(start), start});

    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int cur = p.second;
        ll t_now = p.first;
        if (dist.at(cur) < p.first) continue;
        for (auto &x : G.at(cur)) {
            ll cost = get_cost(x.c, x.d, t_now);
            if (dist.at(x.to) <= dist.at(cur) + cost) continue;
            dist.at(x.to) = dist.at(cur) + cost;
            pq.emplace(P{dist.at(x.to), x.to});
        }
    }
    return dist;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<edge>> G(n);
    rep(i, m) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        a--, b--;
        G[a].emplace_back(edge{(int)b, c, d});
        G[b].emplace_back(edge{(int)a, c, d});
    }

    const auto &res = dijkstra(0, G);
    if (res[n - 1] == INF) {
        cout << -1 << endl;
    } else {
        cout << res[n - 1] << endl;
    }
}
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int mod = 1'000'000'007;

int main() {
    int r1, c1, r2, c2, ans;
    cin >> r1 >> c1 >> r2 >> c2;
    int r_diff = r1 - r2, c_diff = c1 - c2;

    if (r1==r2 && c1==c2) ans=0;
    else if (r1+c1==r2+c2 || r1-c1==r2-c2 || abs(r1-r2)+abs(c1-c2)<=3) ans=1;
    else if (r1-r_diff+c1-r_diff==r2+c2) ans=2;
    else if (r1-c1==r2-c2) ans=2;
    else if (abs(c1+r_diff-c2)<=3) ans=2;
    else if (abs(r1-r_diff-r2)+abs(c1-r_diff-c2)<=3) ans=2;
    else if (abs(r1-r2)+abs(c1-c2)<=6) ans=2;
    else if ((r1+c1)%2==(r2+c2)%2) ans=2;
    else ans=3;
    cout << ans << endl;
    return 0;
}