#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;

const ull P = 1e9 + 7;

ull k1, k2;

ull rng() {
    ull k3 = k1, k4 = k2;
    k1 = k4;
    k3 ^= k3 << 23;
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

struct Edge {
    int u, v;
    ull w;
};

bool operator<(const Edge &x, const Edge &y) {
    return x.w < y.w;
}

void solve() {
    int n, m;
    cin >> n >> m >> k1 >> k2;
    vector<Edge> a(m);

    vector<int> p(n), sz(n, 1);
    iota(p.begin(), p.end(), 0);
    int nset = n;
    auto find = [&](auto &&self, int u) {
        if (u == p[u]) return u;
        return p[u] = self(self, p[u]);
    };
    auto merge = [&](int u, int v) {
        int ru = find(find, u), rv = find(find, v);
        if (ru == rv) return false;
        if (sz[ru] > sz[rv]) swap(ru, rv);
        p[ru] = rv;
        sz[rv] += sz[ru];
        nset--;
        return true;
    };

    for (int i = 0; i < m; i++) {
        a[i].u = rng() % n;
        a[i].v = rng() % n;
        a[i].w = rng();
    }

    if (n == 2) {
        ull mnw = -1;
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (a[i].u == a[i].v) continue;
            mnw = min(mnw, a[i].w);
        }
        for (int i = 0; i < m; i++) {
            if (a[i].u == a[i].v) continue;
            if (a[i].w == mnw) cnt++;
        }
        cout << (ull)((__int128)cnt * mnw % P) << endl;
        return;
    }

    multiset<Edge> pq;
    for (int i = 0; i < n; i++) {
        pq.emplace(a[i]);
    }

    ull ans = 0;
    for (int i = 1; i < n; i++) {
        auto [u, v, w] = *pq.begin();
        cout << u << ' ' << v << ' ' << w << endl;
        pq.extract(pq.begin());
        if (!merge(u, v)) continue;
        ans = ((__int128)ans + w) % P;
    }
    cout << (nset == 1 ? ans : 0) << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int t;
    cin >> t;
    for (; t; t--) solve();

    return 0;
}