#include <bits/stdc++.h>
#define For(i,l,r) for (register int i=l; i<=r; i++)
using namespace std;
typedef unsigned long long LL;
typedef signed long long ll;
template <typename T>
inline void read(T &x) {
    char c = getchar(); int w = 1; x = 0;
    while (!isdigit(c))
        (c == '-') && (w = -w), c = getchar();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ '0'), c = getchar();
    x *= w;
}

const int N = 105;
const ll mod = 998244353;
int T, n, m, k, u, v, w, G[N][N], deg[N];
struct Node {
    int val[N<<1][N<<1];
    Node() { memset(val, 0, sizeof(val)); }
    inline Node operator * (const Node &b) const {
        Node c;
        for (register int k=1; k<=n<<1; ++k) {
            for (register int j=1; j<=n<<1; ++j) {
                if (!b.val[k][j]) continue;
                for (register int i=1; i<=n<<1; ++i) {
                    c.val[i][j] = (c.val[i][j] + 1ll * val[i][k] * b.val[k][j] % mod) % mod;
                }
            }
        }
        return c;
    }
//    Node operator * (const Node &oth) const
//    {
//        Node res;
//        for(int i = 1; i <= n * 2; i++)
//            for(int j = 1; j <= n * 2; j++)
//                for(int k = 1; k <= n * 2; k++)
//                    res.val[i][j] = (res.val[i][j] + (ll)val[i][k] * oth.val[k][j]) % mod;
//        return res;
//    }
};
inline ll ksm(ll x, ll k) {
    ll res = 1;
    while (k) {
        if (k & 1) res = res * x % mod;
        x = x * x % mod; k >>= 1;
    }
    return res;
}
signed main() {
//    int T = 1;
    read(T);
    while (T -- > 0) {
        read(n); read(m); read(k);
        for (register int i=1; i<=n; ++i) {
            for (register int j=1; j<=n; ++j) {
                G[i][j] = -1;
            }
            deg[i] = 0;
        }
        for (register int i=1; i<=m; ++i) {
            read(u); read(v); read(w);
            G[u][v] = G[v][u] = w;
            deg[u] ++; deg[v] ++;
        }
        Node trans;
        for (register int i=1; i<=n; ++i) {
            ll inv = ksm(deg[i], mod-2);
//            cout << inv << endl;
            for (register int j=1; j<=n; ++j) {
                if (~G[i][j]) {
                    if (!G[i][j]) {
                        trans.val[j][i] = trans.val[j+n][i+n] = inv;
                    }
                    else {
                        trans.val[j+n][i] = trans.val[j][i+n] = inv;
                    }
                }
            }
        }
//        for (register int i=1; i<=n<<1; ++i) {
//            for (register int j=1; j<=n<<1; ++j) {
//                printf("%d ", trans.val[i][j]);
//            }
//        }
        Node ans;
        ans.val[1][1] = 1;
        while (k) {
            if (k & 1) ans = trans * ans;
            trans = trans * trans; k >>= 1;
        }
        cout << ans.val[n<<1][1] << endl;
    }
    getchar();
    return 0;
}