#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <iostream>
#define mod 998244353

using namespace std;

typedef long long ll;

class Mat {
public:
    ll a[205][205];
    int r, c;
    Mat(int _r, int _c) : r(_r), c(_c) {memset(a, 0, sizeof a);}
    Mat operator * (const Mat& rhs) {
        Mat ans(r, rhs.c);
        for(int i = 0; i < r; i++)
            for(int j = 0; j < rhs.c; j++) {
                ll x = 0;
                for(int k = 0; k < c; k++) {
                    x = (x + a[i][k] * rhs.a[k][j]);
                    if(x > (3ll << 61)) x %= mod;
                }
                ans.a[i][j] = x % mod;
            }
        return ans;
    }
};

void mul(const Mat &x, ll* y) {
    ll yy[x.r];
    for(int i = 0; i < x.r; i++) {
        yy[i] = 0;
        for(int j = 0; j < x.c; j++)
            yy[i] = (yy[i] + x.a[i][j] * y[j]) % mod;
    }
    for(int i = 0; i < x.r; i++) y[i] = yy[i];
}

int u[10010], v[10010], w[10010], deg[10010], deginv[10010], n, m, k;

ll powmod(ll x, ll y = mod - 2, ll p = mod) {
    ll ans = 1;
    while(y) {
        if(y & 1) ans = ans * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return ans;
}

ll calc(Mat x, ll y) {
    assert(x.r == x.c);
    ll ans[222];
    memset(ans, 0, sizeof ans);
    ans[n + n - 1] = 1;
    for(int i = 0; (1 << i) <= y; i++, x = x * x)
        if((y >> i) & 1) mul(x, ans);
    return ans[0];
}

void add(ll &x, ll y) {
    x = (x + y) % mod;
}
ll solve() {
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++) deg[i] = 0;
    for(int i = 0; i < m; i++) {
        cin >> u[i] >> v[i] >> w[i];
        u[i]--;
        v[i]--;
        deg[u[i]]++;
        deg[v[i]]++;
    }
    for(int i = 0; i < n; i++) if(deg[i]) deginv[i] = powmod(deg[i]);
    Mat trans = Mat(n * 2, n * 2);
    for(int i = 0; i < m; i++) {
        int ui = u[i], vi = v[i];
        if(w[i] == 0) {
            add(trans.a[ui][vi], deginv[ui]);
            add(trans.a[ui + n][vi + n], deginv[ui]);
            add(trans.a[vi][ui], deginv[vi]);
            add(trans.a[vi + n][ui + n], deginv[vi]);
        } else {
            add(trans.a[ui][vi + n], deginv[ui]);
            add(trans.a[ui + n][vi], deginv[ui]);
            add(trans.a[vi][ui + n], deginv[vi]);
            add(trans.a[vi + n][ui], deginv[vi]);
        }
    }
    return calc(trans, k);
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        printf("%lld\n", (solve() % mod + mod) % mod);
    }
}