#include <bits/stdc++.h>
/* #include <atcoder/lazysegtree> */
#include <iostream>
#include <regex>
using namespace std;
/* using namespace atcoder; */
using pint = pair<int, int>;
using ll = long long;
using ull = unsigned long long;
using vll = vector<long long>;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) \
    for (long long i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) \
    for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define VREP(s, ite) for (auto ite = s.begin(); ite != s.end(); ++ite)
#define FI first
#define SE second
#define ALL(v) v.begin(), v.end()
#define endl "\n"
#define ciosup  \
    cin.tie(0); \
    ios::sync_with_stdio(false);
#define eb emplace_back
#define vint vector<int>
constexpr ll INF = 1e15 + 7LL;
constexpr ll MOD = 998244353LL;
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (int i = 0; i < v.size(); ++i) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    if (v.size() == 0) return os;
    for (int i = 0; i < v.size() - 1; ++i) {
        os << v[i] << " ";
    }
    os << v[v.size() - 1];
    return os;
}
template <typename... T>
void In(T&&... args) {
    (std::cin >> ... >> args);
}
template <typename T, typename ...Tail>
void Out(T head, Tail... tail) {
    std::cout << head;
    if constexpr(sizeof...(tail) > 0) {
        std::cout << ' ';
        Out(tail...);
    } else {
        std::cout << '\n';
    }

}

ll sq_ll(ll x) {
    ll lo = 0, hi = 3e9;
    while (hi - lo > 1) {
        ll mid = (hi + lo) / 2LL;
        if (mid*mid <= x) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

ll helper1(ll x) {
    if (x < 0) {
        x += abs(x) % 10000;
    } else if (x > 0) {
        if (x % 10000 != 0)
            x += 10000 - (x % 10000);
    }
    return x;
}

ll helper2(ll x) {
    if (x > 0) {
        x -= x % 10000;
    } else if (x < 0) {
        if (abs(x) % 10000 != 0)
            x -= 10000 - (abs(x) % 10000);
    }
    return x;
}

void solve() {
    double x,y,r; In(x,y,r);
    ll xi = round(x*10000), yi = round(y*10000), ri = round(r*10000); 
    ll up = yi + ri, down = yi - ri;
    while (abs(down) % 10000 != 0) ++down;
    ll ans = 0, cur = down;
    while (cur <= up) {
        ll xwidsq = ri*ri - (yi-cur)*(yi-cur);
        ll xwid = sq_ll(xwidsq);
        ll xlow = helper1(xi - xwid)/10000LL, xup = helper2(xi + xwid)/10000LL;
        if (xup >= xlow) ans += xup - xlow + 1;

        cur += 10000;
    }
    Out(ans);
}


int main() {
    solve();
    char tmp;
    while (cin >> tmp) {
        cin.putback(tmp);
        solve();
    }
}


#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds; //required
using namespace std;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x) cout << #x << " is " << x << "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define flush cout.flush()
typedef long long ll;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;

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

// earliest time
ll calc(ll t0, ll c, ll d){
    ll mid = max(t0 + 1, (ll) sqrt(d));
    ll res = c + t0 + d / (t0 + 1);
    res = min(res, c + (mid - 1) + d / mid);
    res = min(res, c + (mid) + d / (mid + 1));
    res = min(res, c + (mid + 1) + d / (mid + 2));
    return res; 

    // ll lo = t0 + 1, hi = d + 1;
    // if (lo < hi){
    //     ll mid = lo + (hi - lo) / 2;
    //     if (d / (mid + 1) - d / (mid + 2) > 1){
    //         lo = mid + 1;
    //     }
    //     else{
    //         hi = mid;
    //     }
    // }
    // debug(lo);
    // return c + lo + d / (lo + 1);
}

int main(){
    fast;
    int n, m;
    cin >> n >> m;
    vector<vector<tuple<int, ll, ll>>> edges(n + 1);
    vector<ll> time(n + 1, INF);
    vector<bool> vis(n + 1, false);
    time[1] = 0;
    int a, b;
    ll c, d;
    for (int i = 0; i < m; ++i){
        cin >> a >> b >> c >> d;
        if (a != b){
            edges[a].emplace_back(make_tuple(b, c, d));
          	edges[b].emplace_back(make_tuple(a, c, d));
        }
        
    }
    priority_queue<pair<ll, int>> q;
    q.push(make_pair(0, 1));
    int u;
    ll t, tnew;
    while (q.size()){
        t = -q.top().first;
        u = q.top().second;
        q.pop();
        if (vis[u]){
            continue;
        }
        vis[u] = true;
        for (auto [v, c, d]: edges[u]){
            // debug(u);
            // debug(v);
            tnew = calc(t, c, d);
            if (tnew < time[v]){
                time[v] = tnew;
                // cout << ' ' << v << ' ' << tnew << endl;
                q.push(make_pair(-tnew, v));
            }
        }
    }
    // for (int i = 1; i <= n; ++i){
    //     cout << ' ' << time[i];
    // }
    // cout << '\n';
    if (!vis[n]){
        cout << -1 << endl;
    }
    else {
        cout << time[n] << endl;
    }
    return 0;
}