// author: xay5421
// created: Sat Jul 31 14:01:14 2021
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long LL;
const int P=998244353;
const LL PP=1LL*P*P;
int ad(int k1,int k2){return k1+=k2-P,k1+=k1>>31&P;}
int su(int k1,int k2){return k1-=k2,k1+=k1>>31&P;}
int mu(int k1,int k2){return 1LL*k1*k2%P;}
void uad(int&k1,int k2){k1+=k2-P,k1+=k1>>31&P;}
void usu(int&k1,int k2){k1-=k2,k1+=k1>>31&P;}
template<typename... T>int ad(int k1,T... k2){return ad(k1,ad(k2...));}
template<typename... T>void uad(int&k1,T... k2){return uad(k1,ad(k2...));}
template<typename... T>void usu(int&k1,T... k2){return usu(k1,ad(k2...));}
template<typename... T>int mu(int k1,T... k2){return mu(k1,mu(k2...));}
int po(int k1,int k2){
    int k3=1;
    for(;k2;k2>>=1,k1=mu(k1,k1))if(k2&1)k3=mu(k3,k1);
    return k3;
}
template<typename T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<typename T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
int T,n,m,K,f[205][205],e[205][205],g[205][205],sz,deg[205];
void mul(int(*f)[205],int(*g)[205],int(*h)[205]){
    static int res[205][205];
    rep(i,1,sz)rep(j,1,sz)res[i][j]=0;
    rep(i,1,sz)rep(k,1,sz){
        LL t=0;
        rep(j,1,sz){
            t+=1LL*f[i][j]*g[j][k];
            if(t>=PP)t-=PP;
        }
        res[i][k]=t%P;
    }
    rep(i,1,sz)rep(j,1,sz)h[i][j]=res[i][j];
}
int main(){
#ifdef xay5421
    freopen("a.in","r",stdin);
#endif
    rd(T);
    while(T--){
        rd(n),rd(m),rd(K);
        sz=n*2;
        rep(i,1,n)deg[i]=0;
        rep(i,1,sz)rep(j,1,sz)f[i][j]=0,e[i][j]=0;
        rep(i,1,m){
            int k1,k2,k3;
            rd(k1),rd(k2),rd(k3);
            ++deg[k1],++deg[k2];
            if(!k3){
                ++e[k1][k2];
                ++e[k1+n][k2+n];
                swap(k1,k2);
                ++e[k1][k2];
                ++e[k1+n][k2+n];
            }else{
                ++e[k1][k2+n];
                ++e[k1+n][k2];
                swap(k1,k2);
                ++e[k1][k2+n];
                ++e[k1+n][k2];
            }
        }
        rep(i,1,n){
            int t=po(deg[i],P-2);
            rep(j,1,n*2)e[i][j]=mu(e[i][j],t),e[i+n][j]=mu(e[i+n][j],t);
        }
        rep(i,1,sz)rep(j,1,sz)f[i][j]=i==j;
        while(K){
            if(K&1){
                mul(f,e,f);
            }
            K>>=1;
            mul(e,e,e);
        }
        printf("%d\n",f[1][n+n]);
    }
    return 0;
}