#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
#pragma GCC optimize("Ofast")
using namespace         std;
#define                 int long long
#define                 double long double
#define                 fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define ArrayFill(arr,a)       memset(arr,a,sizeof arr)
#define                 endl '\n'              
#define countBit(x)     __builtin_popcountll(x)
#define all(x)          x.begin() , x.end()
#define ln              cout<<'\n';
using namespace std;
using namespace __gnu_pbds;  
typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> oset; 

int ceil(int a,int b){return (a+b-1)/b;}
#define sim template < class c
#define ris return * this
#define dor > debug_ & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug_&>::type operator<<(c i) {
sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...);
struct debug_ {~debug_() { cerr << endl; }eni(!=) cerr << boolalpha << i; ris; }eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {ris << "(" << d.first << ", " << d.second << ")";}
sim dor(rge<c> d){*this << "[";for (auto it = d.b; it != d.e; ++it)*this << ", " + 2 * (it == d.b) << *it;ris << "]";}};
#define db(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define debug(x) debug_() << db(x)

const int MOD = 1000000007ll;
const int N = 1e5+100;
const int inf = 1e18;

vector<array<int,3>> graph[N];

signed main(){
    fast;
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        graph[a].push_back({b,c,d});
        graph[b].push_back({a,c,d});
    }
    set<array<int,2>> q;

    q.insert({0,x});
    vector<int> dist(n+1,inf);
    dist[x] = 0;
    while(!q.empty()){
        auto cur = *q.begin();
        q.erase(cur);
        int cost = cur[0];

        for(auto u: graph[cur[1]]){
            int nx = u[0];
            int t = u[1];
            int md = u[2];
            int cst = (md - (dist[cur[1]]%md))%md;
            t+=cst;
            
            if(dist[cur[1]] + t < dist[nx]){
                q.insert({dist[cur[1]] + t, nx});
                dist[nx] = dist[cur[1]] + t;
            
            }
        }
    }
    if(dist[y]>1e17)dist[y]=-1;
    cout << dist[y];ln;
    
    return 0;
}
#include <bits/stdc++.h>
using namespace std;

#define FORI(i, a, b) for (int i = (int)a; i <= (int)b; i++)
#define FORD(i, a, b) for (int i = (int)a; i >= (int)b; i--)
#define PB push_back
#define ALL(v) v.begin(),v.end()
#define OJ \
    freopen("input.txt", "r", stdin); \
    freopen("output.txt", "w", stdout);
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pii> vpii;

const ll MAX = 1e16;

struct Edge{
    ll to, t, k;
};

ll dijkstra(vector<vector<Edge>>& graph, int x, int y) {
    vll distTo(graph.size(), MAX);
    set<pair<ll, ll>> st;
    distTo[x] = 0;
    st.insert({0, x});
    while (st.size() > 0) {
        // cout << "in side\n";
        pair<ll,ll> cur = *st.begin();
        st.erase(st.begin());
        if (cur.second == y) break;
        int curVertex = cur.second;
        ll curDis = cur.first;
        // cout << "ver: " << curVertex << endl;
        // cout << "dis: " << curDis << endl;
        for (auto adj : graph[curVertex]) {
            ll distToAdj = distTo[adj.to];
            ll waitTime = 0;
            if (curDis % adj.k != 0) {
                waitTime = adj.k - curDis % adj.k;
            }
            if (curDis + adj.t + waitTime <= distTo[adj.to]) {
                distTo[adj.to] = curDis + adj.t + waitTime;
                if (st.count({distToAdj, adj.to})) {
                    st.erase({distToAdj, adj.to});
                }
                st.insert({distTo[adj.to], adj.to});
            }
        }
    }
    // FORI(i, 0, distTo.size() - 1) {
    //     cout << "dist to " << i << " : " << distTo[i] << endl;
    // }
    // cout << "Here\n";
    return distTo[y];
}

int main() {
    int n, m, x, y; cin >> n >> m >> x >> y;
    x--, y--;
    vector<vector<Edge>> graph(n, vector<Edge>());
    FORI(i, 1, m) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        a--, b--;
        graph[a].push_back({b, c, d});
        graph[b].push_back({a, c, d});
    }
    ll ans = dijkstra(graph, x, y);
    if (ans == MAX) cout << -1;
    else cout << ans;
    return 0;
}