#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
long long e[205][205],in[205];
long long A[205][205],c[205][205];
long long inv(int x){
    return x==1?1:(mod-mod/x)*inv(mod%x)%mod;
}
void qpow(int n,int k){
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)A[i][j]=(i==j);
    for(;k;k>>=1){
        if(k&1){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    c[i][j]=0;
                    for(int k=0;k<n;k++)c[i][j]+=A[i][k]*e[k][j]%mod;
                    c[i][j]%=mod;
                }
            }
            for(int i=0;i<n;i++)for(int j=0;j<n;j++)A[i][j]=c[i][j];
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                c[i][j]=0;
                for(int k=0;k<n;k++)c[i][j]+=e[i][k]*e[k][j]%mod;
                c[i][j]%=mod;
            }
        }
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)e[i][j]=c[i][j];
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=0;i<n;i++)in[i]=0;
        for(int i=0;i<2*n;i++)for(int j=0;j<2*n;j++)e[i][j]=0;
        for(int i=0;i<m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            u--,v--;
            in[u]++,in[v]++;
            if(w==1){
                e[u<<1|1][v<<1]=e[u<<1][v<<1|1]=1;
                e[v<<1|1][u<<1]=e[v<<1][u<<1|1]=1;
            }
            else{
                e[u<<1][v<<1]=e[u<<1|1][v<<1|1]=1;
                e[v<<1][u<<1]=e[v<<1|1][u<<1|1]=1;
            }
        }
        for(int i=0;i<n;i++){
            if(!in[i])continue;
            int r=inv(in[i]);
            for(int j=0;j<2*n;j++){
                e[i<<1][j]*=r;
                e[i<<1|1][j]*=r;
            }
        }
        qpow(2*n,k);
        printf("%d\n",A[0][2*n-1]);
    }
}