//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
#define mod 998244353
//#pra gma G CC opti mize(3)
using namespace std;
using std::bitset;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
    template<class T>
    inline void read(T &x) {
        x=0;
        bool fu=0;
        char ch=0;
        while(ch>'9'||ch<'0') {
            ch=getchar();
            if(ch=='-')fu=1;
        }
        while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
        if(fu)x=-x;
    }
    inline int read() {
        int x=0;
        bool fu=0;
        char ch=0;
        while(ch>'9'||ch<'0') {
            ch=getchar();
            if(ch=='-')fu=1;
        }
        while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
        return fu?-x:x;
    }
    template<class T,class... Args>
    inline void read(T& t,Args&... args) {
        read(t);
        read(args...);
    }
    char _n_u_m_[40];
    template<class T>
    inline void write(T x ) {
        if(x==0){
            putchar('0');
            return;
        }
        T tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar('-') ;
        register int cnt = 0 ;
        while( tmp > 0 ) {
            _n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
    }
    template<class T>
    inline void write(T x ,char ch) {
        write(x);
        putchar(ch);
    }
}
using namespace fastIO;
long long inv[3002];
void init_inv(int n){
    inv[1] = 1;
    for(int i = 2;i <= n;i++)  inv[i] = (mod -  mod / i) * inv[mod % i] % mod;
}
int n,m,t1,t2,t3,dp[2][102][2];
int ed[102][102],cnt[102];
template<int N,int M>
struct mat {
    long long v[N+1][M+1];
    mat() {
        memset(v,0,sizeof(v));
    }
     long long & operator()(register int xpos,register int ypos) {
        return v[xpos][ypos];
    }
     long long * operator[](register int xpos) {
        return v[xpos];
    }
    inline int Nsize() {
        return N;
    } inline int Msize() {
        return M;
    }
};
mat<200,200>qwq;
template<int N,int M,int K>
inline mat<N,K> operator*(mat<N,M> a,mat<M,K> b) {
    mat<N,K>rt;
    for(register int i=1; i<=N; i++) {
        for(register int j=1; j<=K; j++) {
            for(register int k=1; k<=M; k+=8) {
                rt.v[i][j]+=a.v[i][k]*b.v[k][j];
                rt.v[i][j]+=a.v[i][k+1]*b.v[k+1][j];
                rt.v[i][j]+=a.v[i][k+2]*b.v[k+2][j];
                rt.v[i][j]+=a.v[i][k+3]*b.v[k+3][j];
                rt.v[i][j]+=a.v[i][k+4]*b.v[k+4][j];
                rt.v[i][j]+=a.v[i][k+5]*b.v[k+5][j];
                rt.v[i][j]+=a.v[i][k+6]*b.v[k+6][j];
                rt.v[i][j]+=a.v[i][k+7]*b.v[k+7][j];
                rt.v[i][j]%=mod;
            }
        }
    }
    return rt;
}
template<int N,int M>
inline mat<N,M> operator*(mat<N,M> a,long long x) {
    mat<N,M>rt;
    for(register int i=1; i<=N; i++) {
        for(register int j=1; j<=M; j++) {
#ifdef mod
            rt.v[i][j]=a.v[i][j]*x%mod;
#else
            rt.v[i][j]=a.v[i][j]*x;
#endif
        }
    }return rt;
}
template<int N,int M>
inline mat<N,M> operator+(mat<N,M> a,mat<N,M> b) {
    mat<N,M>rt;
    for(register int i=1; i<=N; i++) {
        for(register int j=1; j<=M; j++) {
#ifdef mod
            rt.v[i][j]=((a.v[i][j]+b.v[i][j]<mod)?(a.v[i][j]+b.v[i][j]):(a.v[i][j]+b.v[i][j]-mod));
#else
            rt.v[i][j]=a.v[i][j]+b.v[i][j];
#endif
        }
    }
}
template<int N>
inline mat<N,N> pow(mat<N,N> bot,long long p) {
    mat<N,N>rt;
    F(i,1,N)rt.v[i][i]=1;
    while(p) {
        if(p&1) {
            rt=rt*bot;
        }
        bot=bot*bot,p>>=1;
    }
    return rt;
}
int main() {int k;
    init_inv(3000);
    F(iafasd,1,read()){
    cin>>n>>m>>k;
    memset(cnt,0,sizeof(cnt));memset(ed,0,sizeof(ed));
    memset(qwq.v,0,sizeof(qwq.v));
    F(i,1,m){
        read(t1);read(t2);read(t3);
        ed[t1][t2]=ed[t2][t1]=t3+1;
        ++cnt[t1];++cnt[t2];
    }
    F(i,1,n){
        F(j,1,n){
            if(ed[i][j]==1)qwq[i][j]=qwq[i+n][j+n]=inv[cnt[i]];
            else if(ed[i][j]==2)qwq[i][j+n]=qwq[i+n][j]=inv[cnt[i]];
        }
    }
    write(pow(qwq,k)[1][n+n],'\n');
    }
    
    return 0;
}
/*
10
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
4 4 524287
1 2 1
2 4 0
1 3 0
3 4 0
*/