#include<bits/stdc++.h>
#define debug(x) cerr<<"\tDEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=2e2+10,P=998244353;
int N,n,m,K;
int path[maxn][maxn];

long long qpow(long long p,int q){
    long long res=1;
    while(q){
        if(q&1)res=res*p%P;
        q>>=1;
        p=p*p%P; 
    }
    return res;
}
void add(int &a,int b){
    a=(a+b)%P;
}
int cnt[maxn];
int dis[2][maxn][maxn][21];
int dp[2][maxn][2];
int main(){
    int QuQ;cin>>QuQ;
    while(QuQ--){
//        n=100;
//        K=1e6-1;
        cin>>n>>m>>K;
        N=n<<1|1;
        memset(path,-1,sizeof(path));
        for(int i=1;i<=n;i++)
            cnt[i]=0;
        
//        for(int i=1;i<=n;i++)
//            for(int j=i+1;j<=n;j++){
//                path[i][j]=1;
//                path[j][i]=1;
//                cnt[i]++;
//                cnt[j]++;
//            }
        for(int i=1,x,y,z;i<=m;i++){
            scanf("%d%d%d",&x,&y,&z);
            path[x][y]=path[y][x]=z;
            cnt[x]++;
            cnt[y]++;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                dis[0][i][j][0]=0;
                dis[1][i][j][0]=0;
                if(path[i][j]==-1)
                    continue;
                dis[path[i][j]][i][j][0]=qpow(cnt[i],P-2); 
            }
//        debug(dis[1][1][2][0]);
        for(int i=1;i<20;i++){
            for(int s=1;s<=n;s++){
                for(int t=1;t<=n;t++){
                    dis[0][s][t][i]=dis[1][s][t][i]=0;
                    for(int k=1;k<=n;k++){
                        dis[0][s][t][i]=(dis[0][s][t][i]+1LL*dis[0][s][k][i-1]*dis[0][k][t][i-1]+1LL*dis[1][s][k][i-1]*dis[1][k][t][i-1])%P;
                        dis[1][s][t][i]=(dis[1][s][t][i]+1LL*dis[1][s][k][i-1]*dis[0][k][t][i-1]+1LL*dis[0][s][k][i-1]*dis[1][k][t][i-1])%P;
                    }
                }
            }
        }
        bool cur=0;
        memset(dp,0,sizeof(dp));
        dp[0][1][0]=1;
        for(int i=19;i>=0;i--){
            if(1<<i&K){
                cur^=1;
                memset(dp[cur],0,sizeof(dp[cur]));
                for(int s=1;s<=n;s++)
                    for(int t=1;t<=n;t++){
                        add(dp[cur][t][0],1LL*dp[cur^1][s][0]*dis[0][s][t][i]%P);
                        add(dp[cur][t][0],1LL*dp[cur^1][s][1]*dis[1][s][t][i]%P);
                        add(dp[cur][t][1],1LL*dp[cur^1][s][1]*dis[0][s][t][i]%P);
                        add(dp[cur][t][1],1LL*dp[cur^1][s][0]*dis[1][s][t][i]%P);
                    }
            }
        }
        cout<<dp[cur][n][1]<<endl;
    }
    return 0;
}
/*
1
4 4 2
1 2 1
2 4 0
1 3 0
3 4 0
*/