#include<bits/stdc++.h> 
#define int long long
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define endl "\n"
using namespace std;

const int max_n = 2100;
const int max_len = 631441 + 100000;
const int max_sum = 1e7+100;
const int offset = 1e5+10;
const int inf = 1e18;
const int Mod = 3e12+7;
const int max_k = 18;

int n,m;
vector<pair<int,int> > adj[max_n];
int dist[max_n][max_n];

void fill(int s){
	for(int i=0;i<n;i++){
		dist[s][i]=inf;
	}
	dist[s][s]=0;

	bool visited[n];
	memset(visited,0,sizeof(visited));

	priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > > p;
	p.push({dist[s][s],s});

	while(p.size()>0){
		int c = p.top().second;
		p.pop();

		if(visited[c]) continue;
		visited[c]=1;

		for(pair<int,int> x:adj[c]){
			if(dist[s][x.first]>dist[s][c]+x.second){
				dist[s][x.first]=dist[s][c]+x.second;
				// p.push({x.first,dist[s][x.first]});
				p.push({dist[s][x.first],x.first});
			}
		}
	}

	return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   	cin>>n>>m;
   	for(int i=0;i<m;i++){
   		int x,y,c;cin>>x>>y>>c;
   		x--;y--;
   		adj[x].pb({y,c});
   	}
   	for(int i=0;i<n;i++) fill(i);

   	// for(int i=0;i<n;i++){
   	// 	cout<<dist[0][i]<<endl;
   	// }

   	for(int i=0;i<n;i++){
   		int ans=inf;
   		for(pair<int,int> c:adj[i]) if(c.first==i){
   			ans=min(ans,c.second);
   		}
   		for(int j=0;j<n;j++) if(j!=i){
   			ans=min(ans,dist[i][j]+dist[j][i]);
   		}

   		if(ans==inf) cout<<-1<<endl;
   		else cout<<ans<<endl;
   	}

}
/*
ID: hedichehaidar
TASK: photo
LANG: C++11
*/

#include<bits/stdc++.h>
typedef long long ll;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

const int INF = 1000*1000*1000; // 1 e 9
const int MOD = INF + 7;
const double EPS = 0.000000001; // 1 e -9
const ll inf = (ll)1e18;
ll powe(ll u , ll v , ll mod = MOD){
    ll acc = u;
    ll res = 1;
    while(v){
        if(v % 2){
            res = (res * acc)%mod;
        }
        v /= 2;
        acc = (acc * acc)%mod;
    }
    return res;
}
int n , m , x , y;
vector<tuple<int , ll , ll>> adj[(int)1e5 +10];
ll dist[(int)1e5 +10];
bool vis[(int)1e5 +10];
set<pll> s;
void dijkastra(int node){
    s.insert({0 , node});
    while(!s.empty()){
        pll a = *(s.begin());
        s.erase(s.begin());
        if(vis[a.ss]) continue;
        vis[a.ss] = true;
        for(auto v : adj[a.ss]){
            ll b , t , k;
            tie(b , t , k) = v;
            ll cur;
            if(a.ff == 0 || a.ff % k == 0) cur = a.ff;
            else cur = k + k * (a.ff / k);
            if(cur + t < dist[b]){
                dist[b] = cur + t;
                s.insert({dist[b] , b});
            }
        }
    }
}
int main() {
    //ifstream fin ("race.in");
    //ofstream fout ("race.out");
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>x>>y;
    for(int i = 0 ; i < m ; i++){
        ll a , b , t , k;
        cin>>a>>b>>t>>k;
        adj[a].pb(make_tuple(b , t , k));
        adj[b].pb(make_tuple(a , t , k));
    }
    for(int i = 0 ; i < n + 2 ; i++) dist[i] = inf;
    dist[x] = 0;
    dijkastra(x);
    if(dist[y] == inf) cout << -1 << endl;
    else cout << dist[y] << endl;
    return 0;
}

