#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int mo = 998244353;
const int maxn = 105;
LL inv[maxn];

void init() {
    inv[0] = inv[1] = 1;
    for(int i = 2; i < maxn; i++) {
        inv[i] = (mo - mo / i) * inv[mo % i] % mo;
        //inv[i] = i;
    }    
}

LL mat[2 * maxn][2 * maxn];
LL id[2 * maxn][2 * maxn];


void mulmat(LL A[2 * maxn][2 * maxn], LL B[2 * maxn][2 * maxn], int n) {
    LL tmp[2 * maxn][2 * maxn] = {0};
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(A[i][j])
                for(int k = 1; k <= n; k++) {
                    tmp[i][k] = (tmp[i][k] + A[i][j] * B[j][k]) % mo;
                }
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            A[i][j] = tmp[i][j];
        }
    }
}

int main() {
    init();
    int T;
    scanf("%d", &T);
    while(T--) {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        vector<vector<int>> v[2];
        
        memset(id, 0, sizeof(id));
        memset(mat, 0, sizeof(mat));
        for(int i = 1; i <= 2 * n; i++) {
            id[i][i] = 1;
        }
        
        v[0].resize(n + 1);
        v[1].resize(n + 1);
        int x, y, w;
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &x, &y, &w);
            if(w == 0) {
                v[0][x].push_back(y);
                v[0][y].push_back(x);
            }
            else {
                v[1][x].push_back(y);
                v[1][y].push_back(x);
            }
        }
        
        for(int s = 1; s <= n; s++) {
            int siz = v[0][s].size() + v[1][s].size();
            for(auto &x: v[0][s]) {
                mat[x][s] = (mat[x][s] + inv[siz]) % mo;
                mat[x + n][s + n] = (mat[x + n][s + n] + inv[siz]) % mo;
            }
            for(auto &x: v[1][s]) {
                mat[x][s + n] = (mat[x][s + n] + inv[siz]) % mo;
                mat[x + n][s] = (mat[x + n][s] + inv[siz]) % mo;
            }
        }
//        for(int i = 1; i <= 2 * n; i++) {
//             for(int j = 1; j <= 2 * n; j++) {
//                 printf("%d ",mat[i][j]);
//             }
//             printf("\n");
//        }
        
        while(k) {
            if(k & 1) {
                mulmat(id, mat, 2 * n);        
            }
            k >>= 1;
            mulmat(mat, mat, 2 * n);
        }
        printf("%lld\n", id[2 * n][1]);
    }
    return 0;
}