#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long

const ll mod = 1e9 + 7;

struct Matrix {
    int n, m;
    vector<vector<ll>> a;

    void build(int n, int m) {
        a.assign(n + 1, vector<ll>(m + 1, 0));
        this->n = n, this->m = m;
    }

    void I() {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                a[i][j] = 0;
            }
            a[i][i] = 1;
        }
    }

    Matrix Multi(Matrix mtx) {
        int n = this->n, m = mtx.m;
        int mid = this->m;
        Matrix ans;
        ans.build(n, m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                for(int k = 1; k <= mid; k++) {
                    ans.a[i][j] += this->a[i][k] * mtx.a[k][j] % mod;
                    ans.a[i][j] %= mod;
                }
            }
        }
        return ans;
    }

    Matrix Add(Matrix& mtx) {
        int n = this->n, m = this->m;
        Matrix ans;
        ans.build(n, m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                // cout << i << ' ' << j << endl;
                ans.a[i][j] = (this->a[i][j] + mtx.a[i][j]) % mod;
            }
        }
        // ans.print();
        return ans;
    }

    Matrix Sub(Matrix& mtx) {
        int n = this->n, m = this->m;
        Matrix ans;
        ans.build(n, m);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                ans.a[i][j] = (this->a[i][j] - mtx.a[i][j] + mod) % mod;
            }
        }
        return ans;
    }

    void print() {
        cout << n << ' ' << m << endl;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                cout << a[i][j] << ' ';
            }
            cout << endl;
        }
    }

    void Clear() {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                a[i][j] = 0;
            }
        }
    }
} W, DP, L, R, S[70];

int n, m;
ll l, r;

Matrix qpow(Matrix& w, int t)
{
    int n = w.n;
    Matrix ans;
    ans.build(n, n);
    ans.I();
    Matrix base = w;
    // base.print();ans.print();
    while(t) {
        if(t & 1) {
            ans = ans.Multi(base);
            // ans.print();
        }
        base = base.Multi(base);
        t >>= 1;
    }
    // ans.print();
    return ans;
}

Matrix A, B, W;
void init() {
    cin >> n >> m >> l >> r;
    W.build(n, n);
    B.build(n, n);
    for (int i = 1; i <= m; i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (v > n) {
            B.a[u][v - n] = w;
        } else {
            W.a[u][v] = w;
        }
    }
    A.build(n, n);
    A.I();
    for (int i = 1; i <= n; i ++) {
        A = A.Add(W);
        W = W.Multi(W);
    }
}

void dfs(ll x, Matrix& m, ll pos)
{
    if(x == 0) return;
    ll k = pow(2ll, pos);
    // cout << k << endl;
    while(x < k) {
        k /= 2;
        pos -= 1;
    }
    // cout << x << ' ' << k << endl;
    dfs(x - k, m, pos);
    m = (m.Multi(qpow(W, k))).Add(S[pos]);
    // cout << x - k << endl;
    // m.print();
}

void solve()
{
    init();

}

signed main() {
    // ios::sync_with_stdio(false);
    // cin.tie(nullptr);
    // cout.tie(nullptr);
    ll t;
    cin >> t;
    while(t--)
        solve();
    return 0;
}