#include <bits/stdc++.h>
#define N 21
#define M 101
#define popcnt __builtin_popcount
using namespace std;
using ll = long long;

int n, m;
vector<pair<int, int>> qs[M];
ll dp[1<<N];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	cin>>n>>m;
	for (int i=0; i<m; i++) {
		int x, y, z; cin>>x>>y>>z;
		qs[x].push_back({y, z});
	}

	dp[0] = 1;
	for (int i=1; i<(1<<n); i++) {
		for (int j=0; j<n; j++) {
			if (~i & 1<<j) continue;
			dp[i] += dp[i & ~(1<<j)];
		}

		int x = popcnt(i);
		for (auto [y, z] : qs[x]) {
			int smol = i & ((1<<y) - 1);
			if (popcnt(smol) > z) dp[i] = 0;
		}
	}

	cout<<dp[(1<<n)-1]<<endl;
}

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N = 1e5 + 5;
vector<tuple<int, ll, ll>> G[N];
int n, m, u, v, x, y, vis[N];
ll t, k, d[N];

void bfs() {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
    fill(d, d + N, 1e18);
    d[x] = 0;
    q.push({0, x});
    while (!q.empty()) {
        auto[t, a] = q.top();
        q.pop();
        if (a == y) break;
        if (t > d[a]) continue;
        for (auto[b, t, k]:G[a]) {
            t = (d[a] + k - 1) / k * k + t;
            if (d[b] > t) {
                d[b] = t;
                q.emplace(d[b], b);
            }
        }
    }
}

int main() {
    cin >> n >> m >> x >> y;
    while (m--) {
        cin >> u >> v >> t >> k;
        G[u].emplace_back(v, t, k);
        G[v].emplace_back(u, t, k);
    }
    bfs();
    if (d[y] == 1e18) cout << -1;
    else cout << d[y];
    return 0;
}