#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int T, n, m, k, N;
vector < pair < int, int > > son[110];
struct matrix {
    int a[210][210];
    matrix() { memset(a, 0, sizeof a); }
} res, ans;
inline matrix operator * (const matrix &a, const matrix &b) {
    matrix ans;
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++)
            for (int j = 0; j < N; j++) ans.a[i][j] = (ans.a[i][j] + 1ll * a.a[i][k] * b.a[k][j]) % mod;
    return ans;
}
inline int power(int a, int b) {
    long long res = a, ans = 1;
    for (; b; b >>= 1, res = res * res % mod) if (b & 1) ans = ans * res % mod;
    return ans;
}
inline void Add(int &x, int y) {
    if ((x += y) >= mod) x -= mod;
}
inline void rmain() {
    scanf("%d%d%d", &n, &m, &k);
    res = ans = matrix();
    N = 2 * n;
    for (int i = 0; i < n; i++) son[i].clear();
    for (int i = 0; i < N; i++) ans.a[i][i] = 1;
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        u--, v--;
        son[u].push_back({v, w});
        son[v].push_back({u, w});
    }
    for (int i = 0; i < n; i++) {
        int inv = power(son[i].size(), mod - 2);
        for (auto v : son[i]) {
            if (v.second == 0) {
                Add(res.a[i][v.first], inv);
                Add(res.a[i + n][v.first + n], inv);
            }
            else {
                Add(res.a[i + n][v.first], inv);
                Add(res.a[i][v.first + n], inv);
            }
        }
    }
    for (; k; k >>= 1, res = res * res) if (k & 1) ans = ans * res;
    printf("%d\n", ans.a[0][N - 1]);
}
int main() {
    scanf("%d", &T);
    while (T--) rmain();
}