#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=105;
const ll P=998244353;
int tes,n,m,k,dg[M];
ll inv[M];
ll A[2][M],B[2][M][M];
struct edge{
    int x,y,z;
}a[M*M];
void prework(){
    inv[1]=1;
    for(int i=2;i<=100;i++)inv[i]=1ll*(P-P/i)*inv[P%i]%P;
}
void init(){
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        B[0][i][j]=B[1][i][j]=0;
    for(int j=1;j<=n;j++)A[0][j]=A[1][j]=0;
    for(int i=1;i<=n;i++)dg[i]=0;
}
void mulself(ll a[2][M][M],ll b[2][M][M],ll c[2][M][M]){
    ll s[2][M][M];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        s[0][i][j]=s[1][i][j]=0;
    for(int I=0;I<=1;I++)
    for(int J=0;J<=1;J++){
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            (s[I^J][i][j]+=a[I][i][k]*b[J][k][j]%P)%=P;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        c[0][i][j]=s[0][i][j],c[1][i][j]=s[1][i][j];
}
void mul(ll a[2][M],ll b[2][M][M],ll c[2][M]){
    ll s[2][M];
    for(int j=1;j<=n;j++)
        s[0][j]=s[1][j]=0;
    for(int I=0;I<=1;I++)
    for(int J=0;J<=1;J++){
        for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            (s[I^J][j]+=a[I][k]*b[J][k][j]%P)%=P;
    }
    for(int j=1;j<=n;j++)
        c[0][j]=s[0][j],c[1][j]=s[1][j];
}
void qpow(){
    while(k>0){
        if(k&1)mul(A,B,A);
        k>>=1;
        mulself(B,B,B);
    }
}
void solve(){
    scanf("%d%d%d",&n,&m,&k);
    init();
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
        dg[a[i].x]++,dg[a[i].y]++;
    }
    for(int i=1;i<=m;i++){
        B[a[i].z][a[i].x][a[i].y]=inv[dg[a[i].x]];
        B[a[i].z][a[i].y][a[i].x]=inv[dg[a[i].y]];
    }
    A[0][1]=1;
    qpow();
    printf("%lld\n",A[1][n]);
}
int main()
{
    prework();
    scanf("%d",&tes);
    while(tes--)solve();
    return 0;
}