#include<bits/stdc++.h>

using namespace std;
#define ll long long

const int N = 105, P = 998244353;
int T, n, m, k;
vector<pair<int,int>> e[N];
struct matrix{
    int a[N*2][N*2];
    matrix operator*(const matrix &r)const{
        matrix t;
        memset(t.a, 0, sizeof t.a);
        for(int i=1; i<=n*2; ++i) for(int k=1; k<=n*2; ++k) for(int j=1; j<=n*2; ++j)
            t.a[i][j]=(t.a[i][j]+(ll)a[i][k]*r.a[k][j])%P;
        return t;
    }
} a;
int Pow(ll x, int y=P-2){
    int ans=1;
    for(; y; y>>=1, x=x*x%P) if(y&1) ans=ans*x%P;
    return ans;
}
matrix Pow(matrix x, int y){
    matrix ans=x;
    --y;
    for(; y; y>>=1, x=x*x) if(y&1) ans=ans*x;
    return ans;
}
int main() {
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &m, &k);
        while(m--){
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            e[u].emplace_back(v, w);
            e[v].emplace_back(u, w);
        }
        memset(a.a, 0, sizeof a.a);
        for(int i=1; i<=n; ++i){
            int x=Pow(e[i].size());
            for(auto j:e[i])
                (a.a[i][j.first+j.second*n]+=x)%=P,
                (a.a[i+n][j.first+(j.second^1)*n]+=x)%=P;
            e[i].clear();
        }
        printf("%d\n", Pow(a, k).a[1][n+n]);
    }
    return 0;
}