#include<bits/stdc++.h>
#define mod 998244353
#define reg register 
using namespace std;
int T;
int n,m,k,u,v,w;
int g[105][105],d[105];
int A[205][205],f[205][205],a[205][205];

void copy(reg int x[][205],reg int y[][205]){
    for(reg int i=1;i<=2*n;i++){
        for(reg int j=1;j<=2*n;j++) x[i][j]=y[i][j];
    }
}
 
void mul(reg int x[][205],reg int y[][205],reg int z[][205]){
    for(reg int i=1;i<=2*n;i++){
        for(reg int j=1;j<=2*n;j++) x[i][j]=0;
        for(reg int k=1;k<=2*n;k++){
            if(y[i][k]){
                for(reg int j=1;j<=2*n;j++) (x[i][j]+=1ll*y[i][k]*z[k][j]%mod)%=mod;
            }
        }
    }
}

int ksm(reg int x,reg int y){
    reg int res=1;
    while(y){
        if(y&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod,y/=2;
    }
    return res;
}

void jzksm(reg int x){
    memset(A,0,sizeof(A));
    for(reg int i=1;i<=2*n;i++) A[i][i]=1;
    while(x){
        if(x&1){
            mul(a,A,f),copy(A,a);
        }
        mul(a,f,f),copy(f,a);
        x/=2;
    }
}

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&n,&m,&k);
        memset(d,0,sizeof(d));
        memset(g,0,sizeof(g));
        for(reg int i=1;i<=m;i++){
            scanf("%d %d %d",&u,&v,&w);
            g[u][v]=g[v][u]=w+1,d[u]++,d[v]++;
        }
        memset(f,0,sizeof(f));
        for(reg int i=1;i<=n;i++) if(d[i]) d[i]=ksm(d[i],mod-2);
        for(reg int i=1;i<=n;i++){
            for(reg int j=1;j<=n;j++){
                if(g[i][j]==1) f[i*2-1][j*2-1]=f[i*2][j*2]=d[i];
                if(g[i][j]==2) f[i*2-1][j*2]=f[i*2][j*2-1]=d[i];
            }
        }
        jzksm(k);
        printf("%d\n",A[1][2*n]);
    }

    return 0;
}