mooriokart.cpp

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7, two = (mod + 1) / 2;

int pw(int x, int y) {
    int r = 1;
    while (y) {
        if (y & 1) r = 1ll * r * x % mod;
        x = 1ll * x * x % mod;
        y >>= 1;
    }
    return r;
}
int inv(int x) { return pw(x, mod - 2); }

int n, m, x, y;
vector <pair <int, int> > adj[1505];
int a[1505][2505];
int d[1505];
int tot[1505];
vector <int> f;

int dad[1505], sz[1505];
int anc(int u) { return dad[u] == u ? u : dad[u] = anc(dad[u]); }

int main(void) {
    freopen("mooriokart.in", "r", stdin);
    freopen("mooriokart.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> x >> y;
    int cc = n - m;
    y = max(0, y - x * cc);
    for (int i = 1; i <= n; ++i) dad[i] = i, sz[i] = 1;
    for (int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
        u = anc(u), v = anc(v);
        dad[v] = u;
        sz[u] += sz[v];
        sz[v] = 0;
    }
    for (int i = 1; i <= n; ++i) {
        int id = anc(i);
        memset(d, -1, sizeof d);
        queue <int> q;
        d[i] = 0;
        q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto z: adj[u]) {
                int v = z.first, w = z.second;
                if (~d[v]) continue;
                d[v] = d[u] + w;
                tot[id] = (tot[id] + d[v]) % mod;
                if (d[v] < y) ++a[id][d[v]];
                q.push(v);
            }
        }
    }

    //f = a[1] * a[2] * ... * a[n], where a[i] are polynomials
    //lmao brute force passes, NA LUL
    f.assign(y + 1, 0);
    f[0] = 1;
    for (int i = 1; i <= n; ++i) if (dad[i] == i) {
        vector <int> g(y + 1, 0);
        for (int u = 0; u < y; ++u) for (int v = 0; u + v < y; ++v)
            g[u + v] = (g[u + v] + 1ll * f[u] * a[i][v]) % mod;
        f.swap(g);
    }

    int all = 0;
    int ways = 1;
    for (int i = 1; i <= n; ++i) if (dad[i] == i) ways = 1ll * ways * sz[i] % mod * (sz[i] - 1) % mod;
    all = (all + 1ll * x * cc * ways) % mod;
    for (int i = 1; i <= n; ++i) if (dad[i] == i) {
        int ways_i = 1ll * sz[i] * (sz[i] - 1) % mod;
        all = (all + 1ll * tot[i] * ways % mod * inv(ways_i)) % mod;
    }
    int coef = two;
    for (int i = 1; i < cc; ++i) coef = 1ll * coef * i % mod;
    int ans = 0;
    for (int i = 1; i < y; ++i) ans = (ans + 1ll * f[i] * (i + x * cc)) % mod;
    ans = 1ll * (all - ans + mod) * coef % mod;
    cout << ans << endl;
    return 0;
}