#include <bits/stdc++.h>

const int P = 998244353;

int qpow(int a, int b) {
    int s = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            s = 1ll * s * a % P;
        }
        a = 1ll * a * a % P;
    }
    return s;
}

struct matrix {
    int n, m;
    int a[200][200];

    matrix(int _n = 0, int _m = 0) : n(_n), m(_m), a() {}

    int *operator[](int x) {
        return a[x];
    }

    const int *operator[](int x) const {
        return a[x];
    }
};

matrix operator*(const matrix &a, const matrix &b) {
    matrix res(a.n, b.m);
    for (int i = 0; i < a.n; ++i) {
        for (int k = 0; k < b.n; ++k) {
            for (int j = 0; j < b.m; ++j) {
                res[i][j] = (res[i][j] + 1ll * a[i][k] * b[k][j]) % P;
            }
        }
    }
    return res;
}

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    matrix a(2 * n, 2 * n);
    std::vector<int> u(m), v(m), w(m);
    std::vector<int> deg(n);
    for (int i = 0; i < m; ++i) {
        std::cin >> u[i] >> v[i] >> w[i];
        --u[i], --v[i];
        ++deg[u[i]], ++deg[v[i]];
    }
    for (int i = 0; i < m; ++i) {
        a[u[i]][v[i] + w[i] * n] = a[u[i] + n][v[i] + !w[i] * n] = qpow(deg[u[i]], P - 2);
        a[v[i]][u[i] + w[i] * n] = a[v[i] + n][u[i] + !w[i] * n] = qpow(deg[v[i]], P - 2);
    }
    matrix s(1, 2 * n);
    s[0][0] = 1;
    for (; k; k >>= 1) {
        if (k & 1) {
            s = s * a;
        }
        a = a * a;
    }
    std::cout << s[0][2 * n - 1] << "\n";
}

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

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
}