#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define X first
#define Y second
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rep0(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define fore(i,a) for(int i=0;i<a.size();++i)
inline ll rd()
{
    char c=getchar();ll x=0,w=1;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')w=-1,c=getchar();
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x*w;
}
const int N=10005,P=998244353;
inline int pls(int a,int b){a+=b;return a>=P?a-P:a;}
int n,m,K,nn,d[N],iv[N];
struct E{int u,v,w;}e[N]; 
struct mat{int a[205][205];};
inline mat operator*(mat a,mat b)
{
    mat c;
    rep(i,1,nn)rep(j,1,nn)c.a[i][j]=0;
    rep(i,1,nn)rep(k,1,nn)
    {
        int t=a.a[i][k];
        rep(j,1,nn)c.a[i][j]=(c.a[i][j]+1ll*t*b.a[k][j])%P;
    }
    return c;
} 
inline mat pw(mat a,int b)
{
    mat r;rep(i,1,nn)rep(j,1,nn)r.a[i][j]=(i==j);
    for(;b;b>>=1,a=a*a)if(b&1)r=r*a;return r;
}
int main()
{
    int T=rd();iv[1]=1;
    rep(i,2,10000)iv[i]=1ll*(P-P/i)*iv[P%i]%P;
    while(T--)
    {
        n=rd();m=rd();K=rd();nn=n*2;mat a;
        rep(i,1,nn)rep(j,1,nn)a.a[i][j]=0;
        rep(i,1,m)
        {
            int u=rd(),v=rd(),w=rd();
            d[u]++;d[v]++;e[i]=(E){u,v,w};
        }
        rep(i,1,m)
        {
            int u=e[i].u,v=e[i].v,w=e[i].w;
            int p=iv[d[u]],q=iv[d[v]];
            if(w==1)
            {
                a.a[u][n+v]=pls(a.a[u][n+v],p);
                a.a[n+u][v]=pls(a.a[n+u][v],p);
                a.a[v][n+u]=pls(a.a[v][n+u],q);
                a.a[n+v][u]=pls(a.a[n+v][u],q);
            }
            else
            {
                a.a[u][v]=pls(a.a[u][v],p);
                a.a[n+u][n+v]=pls(a.a[n+u][n+v],p);
                a.a[v][u]=pls(a.a[v][u],q);
                a.a[n+v][n+u]=pls(a.a[n+v][n+u],q);
            }
        }
        mat b=pw(a,K);
        printf("%d\n",b.a[1][n+n]);
        rep(i,1,n)d[i]=0;
    }
    return 0;
}
/*
1
8 15 100
1 2 1
1 3 0
2 4 0
2 5 0
2 6 1
2 8 1
3 4 0
3 7 0
3 8 1
4 6 1
5 8 1
5 7 1
6 7 0
6 7 1
7 8 0
*/