#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE
    #define DEBUG
    #include <bits/headerfile.hpp>
#else
    #define zqy1018zqy1018zqy1018zqy1018zqy1018 123
#endif

#define INF 2000000000
#define MOD 998244353
#define MAXN 200005
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> intpair;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
inline int lowbit(int x){
    return x & (-x);
}
inline int modadd(int x, int y){
    return (x + y >= MOD ? x + y - MOD: x + y);
}
inline int sgn(int x){
    return (x < 0 ? -1: (x > 0 ? 1: 0));
}
template<typename T>
T gcd(T a, T b){
    return (!b) ? a: gcd(b, a % b);
}
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
const int ddx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, ddy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

/*--------------------------------------------------------------------*/
/*--------------------------------------------------------------------*/

const int ORD = 205;
int I[ORD][ORD], A[ORD][ORD], tmp[ORD][ORD];
int dim;
void mul(int m1[][ORD], int m2[][ORD], int m3[][ORD]){
    REP(i, 1, dim)
        REP(j, 1, dim){
            m3[i][j] = 0;
            REP(t, 1, dim)
                m3[i][j] = modadd(m3[i][j], 1ll * m1[i][t] * m2[t][j] % MOD);
        }
}
void poww(int mc){
    memset(I, 0, sizeof(I));
    REP(i, 1, dim) I[i][i] = 1;
    while (mc > 0){
        if (mc & 1) mul(I, A, tmp), memcpy(I, tmp, sizeof(tmp));
        mul(A, A, tmp), memcpy(A, tmp, sizeof(tmp));
        mc >>= 1;
    }
}

int n, m, k;
vector<int> G[105][2];
int inv[10005];
void init(){
    n = read(),m =read(), k = read();
    REP(i, 1, n) G[i][0].clear(), G[i][1].clear();
    REP(i, 1, m){
        int u = read(), v = read(),  w= read();
        G[u][w].push_back(v);
        G[v][w].push_back(u);
    }
}
inline void add(int i1, int j1, int i2, int j2, int bb){
    int id1 = i1 << 1;
    if (!j1) --id1;
    int id2 = i2 << 1;
    if (!j2) --id2;
    // A[id1][id2] = modadd(A[id1][id2], bb);
    A[id1][id2] = bb;
}
void solve(){
    REP(i, 1, n + n)
        REP(j, 1, n + n)
            A[i][j] = 0;
            
    REP(i, 1, n){
        int s0 = (int) G[i][0].size();
        int s1 = (int) G[i][1].size();
        int bb = inv[s0 + s1];
        
        // no xor
        for (int v: G[i][0]){
            REP(j, 0, 1)
                add(i, j, v, j, bb);
        }

        for (int v: G[i][1]){
            REP(j, 0, 1)
                add(i, j, v, j ^ 1, bb);
        }
    }

    dim = n + n;
    poww(k);
    int p1 = 1;
    int p2 = n + n;
    printf("%d\n", I[p1][p2]);
}
int main(){
    int T = read();
    inv[1] = 1; 
    REP(i, 2, 10000)
        inv[i] = 1ll * (MOD - MOD / i) * inv[MOD % i] % MOD;
    while (T--){
        init();
        solve();
    }
    return 0;
}