#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long LL;

const int N=210,M=200200;
const LL p=998244353;

int T,n,nn,m,k,deg[N];
int u[M],v[M],w[M];
bool b[N];

struct yy
{
    LL f[N][N];
}t,ans,o;

LL cheng(LL a,LL b)
{
    LL res=1;
    for(;b;b>>=1,a=a*a%p)
    if(b&1)
    res=res*a%p;
    return res;
}

inline yy mul(yy x,yy y)
{
    yy res=o;
    for( int i=1;i<=nn;i++)
    for( int j=1;j<=nn;j++)
    {
        for( int k=1;k<=nn;k++)
        {
            res.f[i][j]+=x.f[i][k]*y.f[k][j];
            if(k%18==0)
            res.f[i][j]%=p;
        }
        res.f[i][j]%=p;
    }
    
    return res;
}

void read(int &hy)
{
    hy=0;
    char cc=getchar();
    while(cc<'0'||cc>'9')
    cc=getchar();
    while(cc>='0'&&cc<='9')
    {
        hy=(hy<<3)+(hy<<1)+cc-'0';
        cc=getchar();
    }
}

int main()
{
    
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        nn=n+n;
        
        for(int i=1;i<=nn;i++)
        for(int j=1;j<=nn;j++)
        ans.f[i][j]=t.f[i][j]=0;
        
        for(int i=1;i<=nn;i++)
        ans.f[i][i]=1;
        
        for(int i=1;i<=n;i++)
        deg[i]=0;
        
        for(int i=1;i<=m;i++)
        {
            read(u[i]);
            read(v[i]);
            read(w[i]);
        
            deg[u[i]]++;
            deg[v[i]]++;
        }
        
        for(int i=1;i<=n;i++)
        deg[i]=cheng(deg[i],p-2);
        
        for(int i=1;i<=m;i++)
        {
            if(w[i]==0)
            {
                t.f[u[i]][v[i]]=(t.f[u[i]][v[i]]+deg[u[i]])%p;
                t.f[v[i]][u[i]]=(t.f[v[i]][u[i]]+deg[v[i]])%p;
                
                t.f[u[i]+n][v[i]+n]=(t.f[u[i]+n][v[i]+n]+deg[u[i]])%p;
                t.f[v[i]+n][u[i]+n]=(t.f[v[i]+n][u[i]+n]+deg[v[i]])%p;
            }
            else
            {
                t.f[u[i]][v[i]+n]=(t.f[u[i]][v[i]+n]+deg[u[i]])%p;
                t.f[v[i]][u[i]+n]=(t.f[v[i]][u[i]+n]+deg[v[i]])%p;
                
                t.f[u[i]+n][v[i]]=(t.f[u[i]+n][v[i]]+deg[u[i]])%p;
                t.f[v[i]+n][u[i]]=(t.f[v[i]+n][u[i]]+deg[v[i]])%p;
            }
        }
        
        for(;k;k>>=1,t=mul(t,t))
        if(k&1)
        ans=mul(ans,t);
        
        cout<<ans.f[1][nn]<<endl;
        
    }
    
    return 0;
}