#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=111111,mod=998244353;
#define fi first
#define se second
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline ll read(){
    char ch=getchar();ll x=0,f=0;
    while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
inline int qpow(int a,int b){
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) ans=1ll*ans*a%mod;
    return ans;
}
int n,m,k,deg[maxn];
struct matrix{
    int a[222][222];
    matrix(){MEM(a,0);}
    matrix operator*(const matrix &t)const{
        matrix ans;
        FOR(i,2,2*n+1) FOR(k,2,2*n+1) FOR(j,2,2*n+1) ans.a[i][j]=(ans.a[i][j]+1ll*a[i][k]*t.a[k][j])%mod;
        return ans;
    }
}A,S;
matrix qpow(matrix a,int b){
    matrix ans;
    FOR(i,2,2*n+1) ans.a[i][i]=1;
    for(;b;b>>=1,a=a*a) if(b&1) ans=ans*a;
    return ans;
}
void solve(){
    n=read();m=read();k=read();
    A=matrix();
    FOR(i,1,n) deg[i]=0;
    while(m--){
        int u=read(),v=read(),w=read();
        deg[u]++;deg[v]++;
        A.a[2*u][2*v+w]=1;
        A.a[2*u+1][2*v+1-w]=1;
        A.a[2*v][2*u+w]=1;
        A.a[2*v+1][2*u+1-w]=1;
    }
    FOR(i,2,2*n+1){
        int inv=qpow(deg[i/2],mod-2);
        FOR(j,2,2*n+1) A.a[i][j]=1ll*A.a[i][j]*inv%mod;
    }
    S=matrix();
    S.a[2][2]=1;
    S=S*qpow(A,k);
    printf("%d\n",S.a[2][2*n+1]);
}
int main(){
    int T=read();
    while(T--) solve();
}