满足 Dijkstra 条件，每次 $u \to v$ 松弛对于 $u$ 的最小到达时间和这条边的最优通过取最大值。

最优通过时间应为使 $t + 1 + \lfloor \frac d {t + 1} \rfloor$ 取最小值的 $t$。

# include <ciso646>
# include <climits>
# include <cmath>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <queue>

namespace Main {
    namespace Source {
        typedef signed int dint;
        typedef short signed int hd;
        typedef long signed int ld;
        typedef long long signed int lld;
        typedef unsigned int uint;
        typedef short unsigned int hu;
        typedef long unsigned int lu;
        typedef long long unsigned int llu;
        typedef double lf;
        typedef long double Lf;
        typedef signed char hhd;
        typedef unsigned char hhu;
        template <typename T>
        static inline const T min(const T& a, const T& b) { return b < a ? b : a; }
        template <typename T>
        static inline const T max(const T& a, const T& b) { return a < b ? b : a; }
        template <typename T> static inline T& min(T& a, T& b) { return b < a ? b : a; }
        template <typename T> static inline T& max(T& a, T& b) { return a < b ? b : a; }
    }
    using namespace Source;
    enum { N = (const uint)1e5, M = (const uint)1e5, D = (const uint)1e9, Log = 29 };
    struct road {
        uint a, b;
        uint c, d;
        uint best;
        inline const void read() { scanf("%u%u%u%u", &a, &b, &c, &d); }
        inline const uint take(const llu gt) { return c + d / (gt + 1); }
    };
    struct city {
        struct road {
            uint id;
            const road* next;
            road() : next(NULL) {}
            road(const uint id, const road* next = NULL) : id(id), next(next) {}
            compl road() { if (next) delete next; }
        };
        llu et;
        road* head;
        city() : et(ULLONG_MAX), head(NULL) {}
        compl city() { if (head) delete head; }
        inline const void add(const uint id) { head = new road(id, head); }
    };
    struct cityp {
        uint p; llu et;
        cityp() {}
        cityp(const uint p, const llu et) : p(p), et(et) {}
        friend inline const bool operator < (const cityp& a, const cityp& b)
        { return a.et > b.et; }
    };
    static uint n, m;
    static road r[M + 1];
    static city c[N + 1];
    static uint best(const uint d) {
        if (d == 0) return 0;
        lf t(sqrt(d));
        const uint ft(t + 1e-9), ct(t + 1 - 1e-9);
        const uint u(ct + d / ct < ft + d / ft ? ct : ft);
        const uint v(u + d / u);
        // printf("%u %lf %u %u\n", d, t, u, v);
        uint r(0);
        for (hu i(Log); i <= Log; --i)
            if ((r | 1 << i) <= u and (r | 1 << i) + d / (r | 1 << i) > v)
                r or_eq 1 << i;
        return r;
    }
    static inline const void solve() {
        std::priority_queue<cityp> h; h.push(cityp(1, c[1].et = 0));
        while (not h.empty()) {
            if (h.top().et not_eq c[h.top().p].et) { h.pop(); continue; }
            const uint t(h.top().p); h.pop();
            for (const city::road* i(c[t].head); i; i = i->next) {
                const llu gt(max(c[t].et, (const llu)r[i->id].best));
                if (gt + r[i->id].take(gt) < c[r[i->id].b].et)
                    h.push(cityp(r[i->id].b, c[r[i->id].b].et = gt + r[i->id].take(gt)));
            }
        }
    }
    static inline const void main() {
        scanf("%u%u", &n, &m);
        for (register uint i(1); i <= m; ++i)
            r[i].read(), r[i].best = best(r[i].d), c[r[i].a].add(i);
        solve();
        printf("%lld\n", c[n].et);
    }
}

signed int main() { Main::main(); return 0; }