#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()


int n, m;
vector<pair<int, int>> edge[100000];
bool vis[100000];
int ans[1000000];

void dfs(int u, int pe, bool pf) {
	vis[u] = true;
	if (pf) {
		ans[u] = (pe + 1) % n;
	}
	else {
		ans[u] = pe;
	}

	for (auto e : edge[u]) {
		int v = e.first;
		if (vis[v])continue;

		dfs(v, e.second, e.second == ans[u]);
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	rep(_, m) {
		int u, v, c;
		cin >> u >> v >> c;
		u--; v--; c--;
		edge[u].emplace_back(v, c);
		edge[v].emplace_back(u, c);
	}

	dfs(0, 0, false);

	rep(i, n) {
		cout << ans[i] + 1 << endl;
	}


	return 0;
}

#include <bits/stdc++.h>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
const ul mod = 1000000007;

ll inf = 1LL << 60;

struct edge {
    ll to, cost, time;
};

void djikstra(vector<ll> &d, vector<ll> &f, vector<vector<edge>> &g, ll start) {
    // p : (cost, position)
    using p = pair<ll, ll>;
    ll inf = 1LL << 60;
    fill(d.begin(), d.end(), inf);
    d[start] = 0;

    priority_queue<p, vector<p>, greater<p>> q;
    q.push(p(0, start));

    for (int i = 0; i < f.size(); i++) {
        f[i] = -1;
    }
    while (!q.empty()) {
        p now = q.top();
        q.pop();
        ll now_cost = now.first, now_position = now.second;
        if (d[now_position] < now_cost)
            continue;
        for (edge e : g[now_position]) {
            ll t = e.time;
            ll d_temp = ((d[now_position] + t - 1) / t) * t;
            if (d[e.to] > d_temp + e.cost) {
                d[e.to] = d_temp + e.cost;
                f[e.to] = now_position;
                q.push(p(d[e.to], e.to));
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n, m, x, y;
    cin >> n >> m >> x >> y;
    x--;
    y--;
    vector<ll> a(m), b(m), t(m), k(m);
    vector<vector<edge>> g(n);
    rep(i, m) {
        cin >> a[i] >> b[i] >> t[i] >> k[i];
        a[i]--;
        b[i]--;
        g[a[i]].push_back({b[i], t[i], k[i]});
        g[b[i]].push_back({a[i], t[i], k[i]});
    }

    vector<ll> d(n, inf), f(n);
    d[x] = 0;
    ll start = x;

    djikstra(d, f, g, start);

    if (d[y] == inf) {
        d[y] = -1;
    }
    cout << d[y] << endl;
    return 0;
}

