#include <bits/stdc++.h>
#define ll long long
#define INF 1000000007
using namespace std;
bool visited[2001];
ll dist[2001];
vector<pair<int,int>> adj[2001];
int edges[2001][2001];
int main()
{
	int N,M;
	cin>>N>>M;
	memset(edges,0,sizeof(edges));
	memset(dist,INF,sizeof(dist));
	for(int i=1; i<=M; i++)
	{
		int A,B;
		ll C;
		cin>>A>>B>>C;
		adj[A].push_back({C,B});
		if(edges[A][B]==0 || C<edges[A][B])
		{	
			edges[A][B]=C;
		}
	}
	priority_queue<pair<int,int>> q;
	
	for(int i=1; i<=N; i++)
	{
		
		dist[i]=0;
		q.push({0,i});
		while(!q.empty())
		{
			long long a=q.top().second;
			q.pop();
			if(visited[a])
			{
				continue;
			}
			visited[a]=true;
			for(auto u: adj[a])
			{
				long long b=u.second;
				long long w=u.first;
				if(dist[a]+w<dist[b])
				{
					dist[b]=dist[a]+w;
					q.push({-dist[b],b});
				}
			}
		}
		ll minn=INF;
		for(int j=1; j<=N; j++)
		{
			if(dist[j]==INF)
			{
				continue;
			}
			if(edges[j][i]>0)
			{
				ll temp= dist[j]+edges[j][i];
				if(temp<minn)
				{
					minn=temp;
				}
			}
		}
		if(minn==INF)
		{
			cout<<"-1"<<endl;
		}
		else
		{
			cout<<minn<<endl;
		}
		memset(visited,false,sizeof(visited));
		for(int j=1; j<=N; j++)
		{
			dist[j]=INF;
		}
		
		
	}
    return 0;
 
}
#include<bits/stdc++.h>
#define ll                  long long
#define dl                 long double
#define pb                push_back
#define F                  first
#define S                  second
#define endl              "\n"
#define rep(i,a,b)       for(i=a;i<b;i++)
#define all(v)             v.begin(),v.end()
#define allr(v)            v.rbegin(),v.rend()
#define mod              1000000007LL
#define CIN(V,s,n)      for(int i=s;i<n;i++){cin >> V[i];}
#define COUT(V,s,n)   {for(int i=s;i<n;i++){cout <<  V[i] << " "  ;} cout << endl;}
#define fast               ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define CLEAR(V);      for(ll i=0;i<V.size();i++) V[i] = 0;
#define N                  200002LL
#define tmod             998244353LL
using namespace std;

bool sBs(const pair<int,int> &a,const pair<int,int> &b)
{   return (a.second < b.second);   }

ll Powb(ll b,ll n,ll m);
ll BS(vector<pair< ll ,ll > > &PS,ll s,ll e,ll ser);
ll MI(ll a, ll m);
ll P[N+1];
void Sieve(int n=N);

vector<vector<ll> > G(N), K(N), T(N);


int main()
{
fast;
ll q=1,t;
//cin >> q; t = q;
while(q--)
{
    ll i,j,n,m,k,l=0,r=0,a=0,b=0,c=0,d=0,e,g=1,p,u,v,w,x,y,z,flag=1;
    //n=m=k=i=j=l=r=a=b=c=d=u=v=w=p=x=y=0;
    cin >> n >> m >> x >> y;
    for (i=0;i<m;i++) {
        cin >> u >> v >> t >> k;
        G[u].pb(v); K[u].pb(k), T[u].pb(t);
        G[v].pb(u); K[v].pb(k), T[v].pb(t);
    }
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>> , greater<pair<ll,ll>> > PQ;
    PQ.push({0,x});
    vector<ll> dist(n+1,-1);
    while(!PQ.empty()) {
        pair<ll,ll> U = PQ.top(); PQ.pop();
        u = U.S;
        w = U.F;
        for (i=0;i<G[u].size();i++) {
            v = G[u][i];
            k = K[u][i];
            t = T[u][i];
            ll nw = t + ((w+k-1)/k)*k;
            if (nw < dist[v] or dist[v] == -1) {
                dist[v] = nw;
                PQ.push({nw,v});
            }
        }
    }

        cout << dist[y];
}
    return 0;
}

//*****************************************************************************************************************************************

ll Powb(ll b,ll n,ll m)
{
    if(n==0) return 1LL;
    if(n==1) return b;
    ll temp = Powb(b,n/2,m);
    if(n%2==0){return (temp*temp)%m;}
    else{return (b*((temp*temp)%m))%m;}
}

ll BS(vector<pair<ll,ll> > &PS,ll s,ll e,ll ser)
{
    if(s>e)
        return s;
    ll mid = (s+e)/2;
    if(PS[mid].F==ser)
    {
        return mid;
    }
    else if(PS[mid].F > ser)
    {
        return BS(PS,s,mid-1,ser);
    }
    else
        return BS(PS,mid+1,e,ser);
}
ll MI(ll a, ll m)
{
    ll m0 = m;
    ll y = 0, x = 1;
    if (m == 1)
      return 0;
    while (a > 1)
    {
        ll q = a / m;
        ll t = m;
        m = a % m, a = t;
        t = y;
        y = x - q * y;
        x = t;
    }
    if (x < 0)
       x += m0;
    return x;
}

void Sieve(int n)
{
    //memset(P,1,sizeof(P));
    P[0] = 0;
    P[1]= 0;
    for(int i=2;i<=n;i++) P[i] = 1;
    for(ll i=2;i*i<=n;i++)
    {
        if(P[i]==1)
        {
            for(ll j=i*i;j<=n;j+=i)
            {
                P[j]=0;
            }
        }
    }

}

