#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
    T s=0; int f=0;
    while(!isdigit(IO=getchar())) f|=IO=='-';
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

bool Mbe;
const int N=1e6+10,INF=1e9+10,P=998244353;

int n,m,k;
int F[210],G[210];
int D[110];

struct Mat{
    int a[210][210];
    void clear(){ memset(a,0,sizeof a); }
    Mat operator * (const Mat _) const {
        Mat res; res.clear();
        /*static ull b[210];
        rep(i,1,n*2) {
            rep(j,1,n*2) if(a[i][j]) {
                rep(k,1,n*2) b[k]+=1ll*a[i][j]*_.a[j][k];
                if(j%18==0) rep(k,1,n*2) res.a[i][k]=(res.a[i][k]+b[k])%P,b[k]=0;
            }
            rep(k,1,n*2) res.a[i][k]=(res.a[i][k]+b[k])%P,b[k]=0;
        }*/
        rep(i,1,n*2) rep(j,1,n*2) if(a[i][j]) rep(k,1,n*2) res.a[i][k]=(res.a[i][k]+1ll*a[i][j]*_.a[j][k])%P;
        return res;
    }
} x;

int I[N];

bool Med;
int main(){ 
    I[0]=I[1]=1;
    rep(i,2,1000) I[i]=1ll*(P-P/i)*I[P%i]%P;
    rep(_,1,rd()) {
        n=rd(),m=rd(),k=rd();
        rep(i,1,n) D[i]=0;
        x.clear();
        rep(i,1,m) {
            int u=rd(),v=rd(),w=rd();
            D[u]++,D[v]++;
            if(w) {
                x.a[u][v+n]++;
                x.a[u+n][v]++;
                x.a[v+n][u]++;
                x.a[v][u+n]++;
            } else {
                x.a[u][v]++;
                x.a[u+n][v+n]++;
                x.a[v][u]++;
                x.a[v+n][u+n]++;
            }
        }
        rep(i,1,n) rep(j,1,n*2) {
            x.a[i][j]=1ll*x.a[i][j]*I[D[i]]%P;
            x.a[i+n][j]=1ll*x.a[i+n][j]*I[D[i]]%P;
        }
        memset(F,0,sizeof F),F[1]=1;
        while(k) {
            if(k&1) {
                rep(i,1,n*2) G[i]=F[i],F[i]=0;
                rep(i,1,n*2) rep(j,1,n*2) F[j]=(F[j]+1ll*G[i]*x.a[i][j])%P;
            }
            k>>=1,x=x*x;
        }
        printf("%d\n",F[n*2]);
    }
}