#include <bits/stdc++.h>

const int mod=998244353;

using namespace std;

int u[10005],v[10005],w[10005],d[105]; 
int add(int x,int y) {
    return (x+=y)>=mod?x-mod:x;
}
struct matrix {
    int a[205][205];
    matrix() {
        for (int i=1;i<=200;i++) {
            for (int j=1;j<=200;j++) {
                a[i][j]=0; 
            }
        }
    }
    matrix operator * (const matrix &x) const {
        matrix ret; 
        for (int i=0;i<=200;i++) {
            for (int j=0;j<=200;j++) {
                for (int k=0;k<=200;k++) {
                    ret.a[i][j]=add(ret.a[i][j],1ll*a[i][k]*x.a[k][j]%mod); 
                }
            }
        }
        return ret; 
    }
} ;

int id(int x,int y) {
    return x*2+y-1; 
}

int Fpw(int x,int k,int p) {
    int ret=1;
    while (k) {
        if (k&1) ret=1ll*ret*x%p; 
        x=1ll*x*x%p; k>>=1; 
    }
    return ret; 
}
matrix fpw(matrix x,int k) {
    matrix ret;
    for (int i=1;i<=200;i++) ret.a[i][i]=1;
    while (k) {
        if (k&1) ret=ret*x;
        x=x*x; k>>=1; 
    }
    return ret; 
}

void solve() {
    int n,m,k;
    scanf("%d %d %d",&n,&m,&k);
    matrix x; 
    for (int i=1;i<=n;i++) d[i]=0; 
    for (int i=1;i<=m;i++) {
        cin>>u[i]>>v[i]>>w[i]; 
        d[u[i]]++,d[v[i]]++;
    }
    for (int i=1;i<=n;i++) {
        if (d[i]!=0) 
            d[i]=Fpw(d[i],mod-2,mod);   
       // cout<<d[i]<<'\n'; 
    }
    for (int i=1;i<=m;i++) {
        for (int o=0;o<2;o++) {
            x.a[id(u[i],o)][id(v[i],o^w[i])]=d[u[i]];
            x.a[id(v[i],o)][id(u[i],o^w[i])]=d[v[i]];
        }
    }
    matrix ans;
    ans.a[1][id(1,0)]=1;
    ans=ans*fpw(x,k);
    printf("%d\n",ans.a[1][id(n,1)]); 
}
int main() {
    int T;
    scanf("%d",&T);
    while (T--) {
        solve(); 
    }
    return 0; 
}