#include<bits/stdc++.h>
using namespace std;

#define Mod(x) (x>=P)&&(x-=P)
#define rep(i,a,b) for(ll i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(ll i=a,i##end=b;i>=i##end;--i)
#define erep(i,a,b) for(ll i=hd[a];i;i=nxt[i])

typedef long long ll;
void Max(ll &x,ll y){x<y&&(x=y);}
void Min(ll &x,ll y){x>y&&(x=y);}

bool vio;
char IO;
ll rd(ll res=0){
    scanf("%d",&res);
    return res;
}
const ll M=215,P=998244353;
ll A[M*M],B[M*M],W[M*M],deg[M];
ll C[M][M];
ll n,m,k;
struct Mtx{
    ll A[M][M];
    Mtx(){memset(A,0,sizeof A);}
    void operator *=(const Mtx &_){
        rep(i,1,2*n)rep(j,1,2*n){
            unsigned long long tmp=0;
            for(ll k=1;k<=iend;k+=6){
                tmp+=1ll*A[i][k]*_.A[k][j];
                tmp+=1ll*A[i][k+1]*_.A[k+1][j];
                tmp+=1ll*A[i][k+2]*_.A[k+2][j];
                tmp+=1ll*A[i][k+3]*_.A[k+3][j];
                tmp+=1ll*A[i][k+4]*_.A[k+4][j];
                tmp+=1ll*A[i][k+5]*_.A[k+5][j];
                //tmp+=1ll*A[i][k+6]*_.A[k+6][j];
                //tmp+=1ll*A[i][k+7]*_.A[k+7][j];
                tmp%=P;
            }
            C[i][j]=tmp;
        }
        rep(i,1,2*n)rep(j,1,2*n)A[i][j]=C[i][j];
    }
    void set(){
        rep(i,1,2*n)A[i][i]=1;
    }
    void clear(){
        rep(i,1,2*n)rep(j,1,2*n)A[i][j]=0;
    }
}f[2];
ll Pow(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=1ll*a*a%P)
        if(b&1)res=1ll*res*a%P;
    return res;
}
Mtx Powm(Mtx a,ll b){
    Mtx res;
    res.set();
    for(;b;b>>=1,a*=a)
        if(b&1)res*=a;
    return res;
}
bool let;
int main(){
    //cerr<<(&vio-&let)/1024.0/1024<<endl;
    rep(cas,1,rd()){
        n=rd(),m=rd(),k=rd();
        rep(i,1,m){
            A[i]=rd(),B[i]=rd(),W[i]=rd();
            ++deg[A[i]],++deg[B[i]];    
        }
        rep(i,1,n)deg[i]=Pow(deg[i],P-2);
        rep(i,1,m){
            ll ta=deg[A[i]],tb=deg[B[i]];
            if(W[i]){
                f[0].A[A[i]][B[i]+n]+=ta;//Pow(deg[A[i]],P-2);
                f[0].A[B[i]][A[i]+n]+=tb;//Pow(deg[B[i]],P-2);
                f[0].A[A[i]+n][B[i]]+=ta;//Pow(deg[A[i]],P-2);
                f[0].A[B[i]+n][A[i]]+=tb;//Pow(deg[B[i]],P-2);
            }else{
                f[0].A[A[i]][B[i]]+=ta;//Pow(deg[A[i]],P-2);
                f[0].A[B[i]][A[i]]+=tb;//Pow(deg[B[i]],P-2);
                f[0].A[A[i]+n][B[i]+n]+=ta;//Pow(deg[A[i]],P-2);
                f[0].A[B[i]+n][A[i]+n]+=tb;//Pow(deg[B[i]],P-2);
            }
        }
        printf("%d\n",Powm(f[0],k).A[1][2*n]);
        f[0].clear();
        rep(i,1,n)deg[i]=0;
    }    
}