#include<bits/stdc++.h>
#define N 105
#define mod 998244353
using namespace std;
int n,m,ed;
int bri[N][N];
bool can[N][N];
long long dp[N][N][23][2],to[N];
int cur;
long long ans[N][N][2][2];
inline void Rd(int &res){
    char c;res=0;
    while(c=getchar(),c<48);
    do res=(res<<3)+(res<<1)+(c^48);
    while(c=getchar(),c>47);
    return;
}
inline long long fastpower(long long a,long long b){
    long long res=1,x=1;
    while(x<b){
        if(x&b)res=res*a%mod;
        x<<=1;a=a*a%mod;
    }
    return res;
}
void init(){
    cur=0;
    memset(bri,-1,sizeof(bri));
    memset(dp,0,sizeof(dp));
    memset(to,0,sizeof(to));
    memset(ans,0,sizeof(ans));
    memset(can,0,sizeof(can));
}
int main(){
//    freopen("data.txt","r",stdin);
    int T;
    Rd(T);
    while(T--){
        Rd(n);Rd(m);Rd(ed);
        init();
        for(int i=1,x,y,z;i<=m;i++){
            Rd(x);Rd(y);Rd(z);
            bri[x][y]=bri[y][x]=z;
            can[x][y]=can[y][x]=1;
            to[x]++;to[y]++;
        }
        for(int i=1;i<=n;i++)to[i]=fastpower(to[i],mod-2);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++)if(can[i][j]){
                dp[i][j][0][bri[i][j]]=to[i];
            }
        }
        for(int i=1;(1<<i)<=ed;i++){
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    for(int l=1;l<=n;l++){
                        dp[j][k][i][0]=(dp[j][k][i][0]+dp[j][l][i-1][0]*dp[l][k][i-1][0]+dp[j][l][i-1][1]*dp[l][k][i-1][1])%mod;
                        dp[j][k][i][1]=(dp[j][k][i][1]+dp[j][l][i-1][1]*dp[l][k][i-1][0]+dp[j][l][i-1][0]*dp[l][k][i-1][1])%mod;
                    }
                }
            }
        }
        ans[1][1][cur][0]=1;
        for(int i=0;(1<<i)<=ed;i++)if((1<<i)&ed){
            for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)ans[j][k][cur^1][0]=ans[j][k][cur^1][1]=0;
            for(int j=1;j<=n;j++){
                for(int k=1;k<=n;k++){
                    for(int l=1;l<=n;l++){
                        ans[j][k][cur^1][0]=(ans[j][k][cur^1][0]+ans[j][l][cur][0]*dp[l][k][i][0]+ans[j][l][cur][1]*dp[l][k][i][1])%mod;
                        ans[j][k][cur^1][1]=(ans[j][k][cur^1][1]+ans[j][l][cur][1]*dp[l][k][i][0]+ans[j][l][cur][0]*dp[l][k][i][1])%mod;
                    }
                }
            }
            cur^=1;
        }
        printf("%lld\n",ans[1][n][cur][1]);
    }
    return 0;
}