#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
#define in(a) a=read()
#define out(a) printf("%d\n",a)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define clr(a,x) memset(a,x,sizeof(a))
inline ll read(){
    char c=getchar();ll f=1,x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+(c-'0'),c=getchar();
    return x*f;
}
#define mod 998244353
void MOD(int &x){x-=x>=mod?mod:0;}
#define maxn 203
#define inf (1<<30)

struct node{
    int a[maxn][maxn];
    int* operator [] (int x){return a[x];}
}f;
int n;
node operator *  (node a,node b){
    node c;
    FOR(i,1,n+n)
        FOR(j,1,n+n)
            c[i][j]=0;
    FOR(i,1,n+n)
        FOR(j,1,n+n)
            FOR(k,1,n+n)
                MOD(c[i][j]+=1ll*a[i][k]*b[k][j]%mod);
    return c;
}
node operator ^ (node a,int b){
    node ans;
    FOR(i,1,n+n)
        FOR(j,1,n+n)
            if(i==j)ans[i][j]=1;
            else ans[i][j]=0; 
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;    
}
int d[maxn];
int power(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
void add(int x,int y){
    d[x]++;
    f[x][y]++;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    int t;
    in(t);
    while(t--){
        int m,k;
        in(n);in(m);in(k);
        FOR(i,1,n+n)d[i]=0;
        FOR(i,1,n+n)
            FOR(j,1,n+n)
                f[i][j]=0;
        FOR(i,1,m){
            int x,y,c;
            in(x);in(y);in(c);
            if(c){
                add(x,n+y),add(y,x+n);
                add(n+y,x),add(n+x,y);
            }
            else{
                add(x,y);add(y,x);
                add(n+x,n+y);add(n+y,n+x);
            }
        }
        FOR(i,1,n+n)
            FOR(j,1,n+n)
                f[i][j]=1ll*f[i][j]*power(d[i],mod-2); 
        f=f^k;
        out(f[1][n+n]);
    }
}