#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int mod = 998244353;
const int maxn = 222;

int f[maxn][maxn], g[maxn][maxn];

int qpow(int a, int n) {
    int ans = 1;
    for ( ; n; n>>=1, a=(ll)a*a%mod) if (n&1) ans=(ll)ans*a%mod;
    return ans;
}
void mul(int f[][maxn], int g[][maxn], int n) {
    static int h[maxn][maxn];
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) h[i][j] = 0;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<n; k++) {
                h[i][k] = (h[i][k] + f[i][j] * (ll)g[j][k]) % mod;
            }
        }
    }
    for (int i=0; i<n; i++) for (int j=0; j<n; j++) f[i][j] = h[i][j];
}

int main(void) {
    //freopen("a.in", "r", stdin);
    int T; scanf("%d", &T);
    while (T--) {
        int n, m, k; scanf("%d%d%d", &n, &m, &k);
        for (int i=0; i<2*n; i++) {
            for (int j=0; j<2*n; j++) f[i][j] = 0, g[i][j] = (i == j);
        }
        for (int i=0; i<m; i++) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            u--, v--;
            f[2*u][2*v^w] = f[2*u^1][2*v^1^w] = 1;
            f[2*v][2*u^w] = f[2*v^1][2*u^1^w] = 1;
        }
        for (int i=0; i<2*n; i++) {
            int sum = 0;
            for (int j=0; j<2*n; j++) sum += f[i][j];
            int tmp = qpow(sum, mod - 2);
            for (int j=0; j<2*n; j++) if (f[i][j]) {
                f[i][j] = tmp;
            }
        }
//        for (int i=0; i<2*n; i++) {
//            for (int j=0; j<2*n; j++) printf("%d ", f[i][j]);
//            puts("");
//        }

        for ( ; k; k>>=1) {
            if (k & 1) mul(g, f, 2*n);
            mul(f, f, 2*n);
        }

        printf("%d\n", g[0][2*n-1]);
    }
    return 0;
}