#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
using namespace std;

const int mo=998244353;
const int N=205;
int power(int x,int y){
    int s=1;
    for (;y;y/=2,x=1ll*x*x%mo)
        if (y&1) s=1ll*s*x%mo;
    return s;
}
int n,m,k;
int a[N][N],c[N][N];
int b[N],d[N];

void Mul2(){
    memset(c,0,sizeof(c));
    for (int i=1;i<=2*n;i++)
        for (int j=1;j<=2*n;j++){
            unsigned long long temp=0;
            for (int k=1;k<=2*n;k++){
                temp+=1ull*a[i][k]*a[k][j];
                if ((k&15)==15) temp%=mo;
            }
            c[i][j]=temp%mo;
        }
    memcpy(a,c,sizeof(a));
}
void Mul1(){
    memset(d,0,sizeof(d));
    for (int i=1;i<=2*n;i++)
        for (int j=1;j<=2*n;j++)
            d[j]=(d[j]+1ll*b[i]*a[i][j])%mo;
    memcpy(b,d,sizeof(b));
}
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    memset(a,0,sizeof(a));
    for (int i=1;i<=m;i++){
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        a[x][y+v*n]++;
        if (x!=y) a[y][x+v*n]++;
        a[x+n][y+n-v*n]++;
        if (x!=y) a[y+n][x+n-v*n]++;
    }
    for (int i=1;i<=2*n;i++){
        int S=0;
        for (int j=1;j<=2*n;j++) S+=a[i][j];
        for (int j=1;j<=2*n;j++) a[i][j]=1ll*a[i][j]*power(S,mo-2)%mo;
    }
    memset(b,0,sizeof(b));
    b[1]=1;
    for (;k;){
        if (k&1) Mul1();
        if (k/=2) Mul2();
    }
    cout<<b[2*n]<<endl;
}
int main(){
    int T;
    scanf("%d",&T);
    while (T--) solve();
}