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

ll mod = 1000000007;

int main() {
    ll N,M,X,Y; cin >> N >> M >> X >> Y;
    Graph G(N+1);
    rep(i,M){
        ll a,b,t,k; cin >> a >> b >> t >> k;
        G[a].push_back(make_tuple(b,t,k));
        G[b].push_back(make_tuple(a,t,k));
    }
    //Dijkstra (普通のダイクストラ)
    priority_queue<Pr, vector<Pr>, greater<Pr>> go;
    ll x,y,a,t,k; ll inf = 2e18;
    ll dist[N+1]; //始点からの距離
    rep(j,N+1){
        dist[j] = inf;
    }
    go.push(make_pair(0,X)); dist[X] = 0; //始点座標:s
    Pr p;
    while(!go.empty()){
        p = go.top(); go.pop();
        x = p.first; y = p.second;
        if(x>dist[y]) continue;
        for(auto q:G[y]){ //G[y]:Graph
            a = get<0>(q); t = get<1>(q); k = get<2>(q);
            ll m = x%k;
            ll st = 0;
            if(m!=0) st = k-m;
            if(x+st+t<dist[a]){
                dist[a] = x+st+t;
                go.push(make_pair(x+st+t,a));
            }
        }
    }
    if(dist[Y]==inf) cout << -1 << endl;
    else cout << dist[Y] << endl;
}
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long long int lli;
typedef vector<ll> vl;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define SQR(x) ((x) * (x))

#define loop(i, y) for (int i = 0; i < int(y); i++)
#define FOR(i, x, y) for (int i = int(x); i <= int(y); i++)
#define ROF(i, y, x) for (int i = int(y); i >= int(x); i--)

#define ALL(c) c.begin(), c.end()
#define CLR(x, y) memset(x, y, sizeof(x))

#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

#define si(x) scanf("%d", &x)
#define sii(x, y) scanf("%d %d", &x, &y)
#define siii(x, y, z) scanf("%d %d %d", &x, &y, &z)
#define sl(x) scanf("%lld", &x)
#define sll(x, y) scanf("%lld %lld", &x, &y)
#define slll(x, y, z) scanf("%lld %lld %lld", &x, &y, &z)
#define sllll(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d)

#define FileIO  freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define FastIO  ios::sync_with_stdio(false); cin.tie(0);

#define FixedPrecision(x) ios::sync_with_stdio(false);cout.setf(ios::fixed); cout.precision(x);cin.tie(0);
#define bitCheck(N, in) ((bool)(N & (1LL << (in))))
#define bitOff(N, in) (N & (~(1LL << (in))))
#define bitOn(N, in) (N | (1LL << (in)))
#define bitFlip(a, k) (a ^ (1LL << (k)))

#define start_time clock_t tStart = clock();
#define execution_time printf("\n>>Time taken: %.10fs\n", (double)(clock() - tStart) / CLOCKS_PER_SEC);

#define popCount(x) __builtin_popcount(x)
#define int2Bin(x, y); bitset<y> z = x; cout << z.to_string() << endl;
#define tr(it, container) for (auto it = container.begin(); it != container.end(); it++)
#define unq(v) (v).erase(unique(ALL(v)), v.end())
#define common(a, b) sort(ALL(a)), sort(ALL(b)), a.erase(set_intersection(ALL(a), ALL(b), a.begin()), a.end())
#define uncommon(a, b) sort(ALL(a)), sort(ALL(b)), a.erase(set_symmetric_difference(ALL(a), ALL(b), a.begin()), a.end())

#define TE(t, n) cout << "Case " << t << ": " << n << endl;



#ifndef ONLINE_JUDGE
    #define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
    template < typename Arg1 >
    void __f(const char* name, Arg1&& arg1){
        cout << name << " = " << arg1 << std::endl;
    }
    template < typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names, ',');
        cout.write(names, comma - names) << " = " << arg1 <<" | ";
        __f(comma+1, args...);
    }
#else
    #define debug(...)
#endif


/// Constants

#define MAXN 1000005
#define MAX 200005
#define MOD 1000000007
#define BASE 1000000009
#define eps 1e-9
#define INF 1llu << 61 // 2,305,843,009,213,693,952
#define inf 1 << 29    // 536,870,912
#define PI acos(-1.0)  // 3.1415926535897932
#define E 2.71828182845904523536




int main()
{

    

    ll T = 1;          //sl(T);



    FOR(t,1,T)
    {
        ll n ; sl (n);

        unordered_map< ull,ull > m1,m2;
        vector < ull > v1,v2;
        
        ull val = 1;

        for(ull i = 0; i <= 37 ; i++){
            val*=3;
            v1.pb(val);
            m1[val]=i+1;
        }
        val = 1;
        for(ull i = 0; i <= 25 ; i++){
            val*=5;
            v2.pb(val);
            m2[val]=i+1;
        }

        for(int i = 0 ; i <=37 ; i++){
            if( m2[n-v1[i]] ){
                cout << i+1 << " " << m2[n-v1[i]];
                return 0;
            }
        }

        
        
        cout << "-1" <<endl;
    }




        return 0;
}