#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define fgx cerr<<"-------------"<<endl
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
void dbg(){cerr<<endl;}
template<typename A,typename... B>void dbg(A x,B... y){cerr<<x<<" ";dbg(y...);}
#define debug(...) cerr<<#__VA_ARGS__<<"=",dbg(__VA_ARGS__)
const int mod=998244353;
int n,d[1000];
struct mat {
    ll a[210][210];
    mat(){memset(a,0,sizeof(a));}
};
inline mat operator *(mat a,mat b) {
    mat c;
    for(rint i=1;i<=n+n;i++)
    for(rint j=1;j<=n+n;j++)
    for(rint k=1;k<=n+n;k++)
    c.a[i][j]+=(ll)a.a[i][k]*b.a[k][j]%mod;
    for(rint i=1;i<=n+n;i++)
    for(rint j=1;j<=n+n;j++) c.a[i][j]%=mod;
    return c;
}
void pr(mat a){for(rint i=1;i<=n+n;i++,cerr<<endl)for(rint j=1;j<=n+n;j++)cerr<<a.a[i][j]<<" ";}
inline int qpow(int x,int y){int A=1;for(;y;y>>=1,x=(ll)x*x%mod)if(y&1)A=(ll)A*x%mod;return A;}
int main()
{    int t; cin>>t;
    while(t--) {
        int m,k,x,y,z; mat _[2],A,B; scanf("%d%d%d",&n,&m,&k);
        for(rint i=1;i<=n;i++) d[i]=0;
        for(rint i=1;i<=m;i++) {
            scanf("%d%d%d",&x,&y,&z);
            _[z].a[x][y]=_[z].a[y][x]=1;
            d[x]++,d[y]++;
        }
        for(rint i=1;i<=n;i++)
        for(rint j=1;j<=n;j++)
        _[0].a[i][j]=(ll)_[0].a[i][j]*qpow(d[j],mod-2)%mod,_[1].a[i][j]=(ll)_[1].a[i][j]*qpow(d[j],mod-2)%mod;
    //    pr(_[1]);
        for(rint i=1;i<=n;i++)
        for(rint j=1;j<=n;j++)
        A.a[i][j]=_[0].a[i][j],A.a[i+n][j]=_[1].a[i][j],A.a[i][j+n]=_[1].a[i][j],A.a[i+n][j+n]=_[0].a[i][j];
        for(rint i=1;i<=n+n;i++) B.a[i][i]=1;
        for(;k;k>>=1,A=A*A) if(k&1) B=B*A;
    //    debug(B.a[3+n][1],B.a[4+n][1],qpow(3,mod-2));
        cout<<B.a[n+n][1]<<"\n";
    }
    return 0;
}