#ifdef _LOCAL
    #include "local_include.hpp"
#else
    #include <bits/stdc++.h>
    using namespace std;
#endif
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

#define fto(i, s, e) for (int i = (s); i <= (e); ++i)
#define fto1(i, s, e) for (int i = (s); i < (e); ++i)
#define fdto(i, s, e) for (int i = (s); i >= (e); --i)
#define fit(it, a) for (auto it = (a).begin(); it != (a).end(); ++it)
#define fat(i, a) for (auto i : (a))

#define ll long long
#define ii pair<int, int>
#define pll pair<ll, ll>
template<class T, class Cmp = less<T>> using oss = tree<T, null_type, Cmp, rb_tree_tag, tree_order_statistics_node_update>;

#define bc __builtin_popcountll
#define y1 ansdj
#define endl '\n'
#define ff first
#define ss second
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define bug(...) _bug(cout, __VA_ARGS__)
#define buga(a, s, e) cout << '{'; if (e < s) cout << '}'; else fto (__i, s, e) cout << a[__i] << " }"[__i == e]; cout << endl

template<class T1, class T2> ostream& operator<<(ostream &os, pair<T1, T2> const &v) {
    return os << '(' << v.ff << ", " << v.ss << ')';
}

template<typename T>
void _bug(ostream &os, T const &var) { os << var << endl; }

template<typename T, typename... Args>
void _bug(ostream &os, T const &var, Args const &... args) {
    os << var << ' ';
    _bug(os, args...);
}

double const pi = acos(-1);
#define oo 1000000007
#define OO 1000000000000000003LL
int const maxn = 1e5+3;

void gcd(int a, int b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
    } else {
        gcd(b, a%b, x, y);
        ll tmp = x;
        x = y;
        y = tmp - a/b*y;
    }
}

#define multi_test 1
void _main() {
    int n, s, k;
    cin >> n >> s >> k;
    int g = __gcd(n-s, __gcd(n, k));
    n /= g, s /= g, k /= g;
    g = __gcd(k, n);
    if (g != 1) bug(-1);
    else {
        ll x, y;
        gcd(k, n, x, y);
        x *= (n-s);
        x %= n;
        if (x < 0) x += n;
        bug(x);
    }
}

int main() {
    #ifdef _LOCAL
        freopen("main.inp", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int t = 1;
    if (multi_test) cin >> t;
    while (t--) {
        _main();
    }

    #ifdef _LOCAL
        cerr << 0.001*clock() << endl;
    #endif
    return 0;
}
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
#define rep(i,n) for(ll i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rrep(i,n) for(ll i=n-1; i>=0; i--)
#define fi first
#define se second
#define pcnt __builtin_popcountll
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> PlP;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
string zero_padding(int val, int nf){ ostringstream sout;sout << setfill('0') << setw(nf) << val; return sout.str();};
const ld eps = 1e-10;
ull mo = 1000000007;
ld PI=asin(1)*2;
//using namespace atcoder;

vector<vector<PlP>> G(100010);
int main(){ 
    ll N,M;
    cin >> N >> M;
    vector<ll> A(M), B(M), C(M), D(M);
    rep(i,M){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        A[i]--; B[i]--;
    }
    rep(i,M){
        G[A[i]].push_back({C[i],{D[i],B[i]}});
        G[B[i]].push_back({C[i],{D[i],A[i]}});
    }
    vector<ll> d1(N,1e18);
    priority_queue<Pll, vector<Pll>, greater<Pll>> que;
    que.push(Pll(0,0));
    while(!que.empty()){
        ll t = que.top().fi;
        ll v = que.top().se;
        que.pop();
        if(d1[v] <= t) continue;
        //if(d1[v] != 1e18) continue;
        d1[v] = t;
        for(auto& p:G[v]){
            ll c = p.fi;
            ll d = p.se.fi;
            ll u = p.se.se;
            ll rd1 = max(ll(sqrt(ld(d))-1),ll(t));
            ll rd2 = max(ll(sqrt(ld(d))),ll(t));
            ll tt1 = ll(rd1) + c + ll(d/(rd1+1));
            ll tt2 = ll(rd2) + c + ll(d/(rd2+1));
            // cout << L << " " << R << " " << r1 << " " << r2 << endl;

            que.push(Pll(min(tt1,tt2),u));
        }
    }
    if(d1[N-1] == 1e18){
        drop(-1);
    }
    cout << d1[N-1] << endl;
}
