#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <ctime>
#include <cmath>
#define ll long long
using namespace std;
int T,n,m,k;
struct fs{
    int fz;
    int fm;
};
struct dat{
    int x;
    int y;
    int data[202][202];
}A,B,C;
int ds[202];
const int MOD = 998244353;
int niyuan[102];
int get(){
    char t = getchar();
    while(t < '0' || t > '9')t=getchar();
    int x = 0;
    while(t>='0' && t <= '9'){
        x *= 10;
        x += t-'0';
        t = getchar();
    }
    return x;
}

ll getgcd(ll x, ll y){
    if(x < y)swap(x,y);
    while(x % y){
        ll z = x % y;
        x = y;
        y = z;
    }
    return y;
}

fs Add(fs x, fs y){
//    printf("Add: %lld %lld %lld %lld\n", x.fz, x.fm, y.fz, y.fm);
    fs ans;
    ans.fz = (ll)x.fz * y.fm % MOD + (ll)y.fz * x.fm % MOD;
    ans.fz %= MOD;
    if(ans.fz)
        ans.fm = (ll)x.fm * y.fm % MOD;
    else
        ans.fm = 1;    
    return ans;
}

fs Mult(fs x, fs y){
//    printf("Add: %lld %lld %lld %lld\n", x.fz, x.fm, y.fz, y.fm);
    fs ans;
    ans.fz = (ll)x.fz * y.fz % MOD;
    if(ans.fz)
        ans.fm = (ll)x.fm * y.fm % MOD;
    else
        ans.fm = 1;    
    return ans;
}

void mul(dat &d1, dat &d2, int opt){
    int nn = d1.x;
    int mm = d2.y;
    int t = d1.y;
    if(opt) nn /= 2;
    //dat ans
//    printf("%d %d %d\n",nn,mm,t);
    for(int i=0;i<nn;++i)
        for(int j=0;j<mm;++j){
            C.data[i][j] = 0;
            for(int kk=0;kk<t;++kk){
                C.data[i][j] += (ll)d1.data[i][kk] * d2.data[kk][j] % MOD;
                if(C.data[i][j] > MOD)C.data[i][j] -= MOD;
                
            }
        }
    for(int i=0;i<nn;++i)
        for(int j=0;j<mm;++j){
            d1.data[i][j] = C.data[i][j];
        //    if(opt)d1.data[i+nn][j] = C.data[i][j];
        }
    if(opt){
    for(int i=0;i<nn;++i)
        for(int j=0;j<mm;++j){
            if(j >= nn)d1.data[i+nn][j] = C.data[i][j-nn];
            else d1.data[i+nn][j] = C.data[i][j+nn];
        //    if(opt)d1.data[i+nn][j] = C.data[i][j];
        }        
    }
}
int get_ans(fs x){
    if(x.fz == 0) return 0;
//    printf("")
    int ny = 998244351;
    int ans = x.fz;
    while(ny){
        if(ny & 1){
            ans = (ll)ans * x.fm % MOD;
        }
        x.fm = (ll)x.fm * x.fm % MOD;
        ny = ny >> 1;
    }
    return (int)ans;
}

int get_ny(int x){
    int ny = 998244351;
    int ans = 1;
    while(ny){
        if(ny & 1){
            ans = (ll)ans * x % MOD;
        }
        x = (ll)x * x % MOD;
        ny = ny >> 1;
    }
    return (int)ans;    
}

int main(){
    
    for(int i=1;i<=100;++i)niyuan[i] = get_ny(i);
    niyuan[0] = 0;
    T = get();
    for(int ii=1;ii<=T;++ii){
        A.x = 1;
        n = get();
        m = get();
        k = get();
    //    printf("input: %d %d %d\n",n,m,k);
        A.y = 2*n;
        B.x = 2*n;
        B.y = 2*n;
        for(int i=0;i<2*n;++i){
            A.data[0][i] = 0;
        }    
        A.data[0][0] = 1;
        for(int i=0;i<2*n;++i)for(int j=0;j<2*n;++j){
            B.data[i][j] = 0;
        }
        memset(ds, 0, sizeof(ds));
        for(int i=0;i<m;++i){
            int u,v,w;
            u = get();
            v = get();
            w = get();
            ++ ds[u-1];
            ++ ds[v-1];
            if(w){
                B.data[u-1][v+n-1] = 1;
                B.data[v-1][u+n-1] = 1;
                B.data[u+n-1][v-1] = 1;
                B.data[v+n-1][u-1] = 1;                                 
            }else{
                B.data[u-1][v-1] = 1;
                B.data[v-1][u-1] = 1;
                B.data[u+n-1][v+n-1] = 1;
                B.data[v+n-1][u+n-1] = 1;                        
            }
        }
        for(int i=0;i<2*n;++i)for(int j=0;j<2*n;++j){
            if(B.data[i][j]){
                if(i < n)B.data[i][j] = niyuan[ds[i]];
                else B.data[i][j] = niyuan[ds[i-n]];
            //    printf("%d %d %d\n", i,j,B.data[i][j]);
            }
        }
    //    printf("init_success\n");
        while(k){
        //    printf("now : %d\n", k);
            if(k & 1)mul(A,B,0);
            mul(B,B,1);
            k = k >> 1;
        //    printf("A: ");
         //   for(int i=0;i<2*n;++i)printf("%d ",A.data[0][i]);
         //   printf("\n");
        }        
        printf("%d\n", A.data[0][2*n-1]);
    }
    return 0;
}