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

const int p = 998244353;

int qpow(int a, int b) {
    if (!b) return 1;
    int t = qpow(1ll * a * a % p, b >> 1);
    return b & 1 ? 1ll * t * a % p : t;
}

int n, m, k, deg[205];

struct node {
    int a[205][205];
    node() {memset(a, 0, sizeof a);}
} s, ss[25];

node mul(const node &x, const node &y) {
    node ans;
    for (int i = 1; i <= 2 * n; i++)
        for (int j = 1; j <= 2 * n; j++) {
            long long tmp = 0;
            for (int k = 1; k <= 2 * n; k++)
                tmp += 1ll * x.a[i][k] * y.a[k][j] % p;
            ans.a[i][j] = tmp % p;
        }
            
    return ans;
}

void solve() {
    scanf("%d %d %d", &n, &m, &k);
    memset(deg, 0, sizeof deg);
    memset(s.a, 0, sizeof s.a);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        deg[u]++;
        deg[v]++;
        deg[u + n]++;
        deg[v + n]++;
        if (w) {
            s.a[u][v + n]++;
            s.a[v][u + n]++;
            s.a[u + n][v]++;
            s.a[v + n][u]++;
        } else {
            s.a[u][v]++;
            s.a[v][u]++;
            s.a[u + n][v + n]++;
            s.a[v + n][u + n]++;
        }
    }
    for (int i = 1; i <= 2 * n; i++)
        for (int j = 1; j <= 2 * n; j++)
            s.a[i][j] = 1ll * s.a[i][j] * qpow(deg[i], p - 2) % p;
        //    printf("%d%c", s.a[i][j], " \n"[j == 2 * n]);
    for (int i = 0; i <= 20; i++) {
        if (i == 0) ss[i] = s;
        else ss[i] = mul(ss[i - 1], ss[i - 1]);
        if ((k - 1) >> i & 1) s = mul(s, ss[i]);
    }
    printf("%d\n", s.a[1][n + n]);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}