#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (int i=(a); i<=(b); i++)
#define per(i,a,b) for (int i=(a); i>=(b); i--)
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
    x=0; char c=getchar(); int f=1;
    while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
    while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
template<class T> inline T Abs(const T &x){return x>0?x:-x;}
inline ui R() {
    static ui seed=416;
    return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 103, mo = 998244353;
const ll MOD=7ll*mo*mo;
int n,m,k,inv[N*N];
vector<Pii>e[N];
struct mtr{
    int a[203][203];
    mtr(){memset(a,0,sizeof(a));}
}I,A;
ll C[203][203];
inline void add(int &x,int y){x=(x+y)%mo;}
inline mtr mul(const mtr&a,const mtr&b){
    memset(C,0,sizeof(C));
    rep(i,1,2*n)rep(j,1,2*n)rep(k,1,2*n){
        C[i][k]+=1ll*a.a[i][j]*b.a[j][k];
        C[i][k]=C[i][k]<MOD?C[i][k]:C[i][k]-MOD;
    }
    mtr c;rep(i,1,2*n)rep(j,1,2*n)c.a[i][j]=C[i][j]%mo;
    return c;
}
int main() {
    inv[1]=1;rep(i,2,N*N-1)inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
    int T;read(T);while(T--){
        read(n);read(m);read(k);
        rep(i,1,n)e[i].clear();
        rep(i,1,m){
            int u,v,w;read(u);read(v);read(w);
            e[u].pb(mp(v,w));e[v].pb(mp(u,w));
        }
        memset(A.a,0,sizeof(A.a));
        rep(i,1,n)rep(j,0,SZ(e[i])-1)rep(k,0,1){
            add(A.a[e[i][j].fi+(k^e[i][j].se)*n][i+k*n],inv[SZ(e[i])]);
        }
        mtr ans;rep(i,1,2*n)ans.a[i][i]=1;
        // int dp[203]={0};dp[1]=1;
        while(k){
            if(k&1)ans=mul(ans,A);
            A=mul(A,A);k>>=1;
        }
        printf("%d\n",ans.a[n*2][1]);
    }
    return 0;
}