#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int N = 205;
const int MOD = 998244353;

int matlen;
struct Mat {
    ll a[N][N];
    Mat() {
        memset(a, 0, sizeof(a));
    }
    Mat operator * (const Mat& rhs) const {
        Mat ans;
        for (int i = 1; i <= matlen; i++) {
            for (int k = 1; k <= matlen; k++) {
                if (a[i][k] == 0) continue;
                for (int j = 1; j <= matlen; j++) {
                    (ans.a[i][j] += a[i][k] * rhs.a[k][j]) %= MOD;
                }
            }
        }
        return ans;
    }
};

Mat PowMod(Mat a, int n) {
    Mat ans;
    for (int i = 1; i <= matlen; i++) ans.a[i][i] = 1;
    while (n) {
        if (n&1) ans = ans * a;
        a = a * a;
        n >>= 1;
    }
    return ans;
}

ll inv[N];
void init() {
    inv[0] = inv[1] = 1;
    for (int i = 2; i < N; i++) {
        inv[i] = MOD - 1LL*(MOD/i)*inv[MOD%i]%MOD;
        assert(inv[i]*i%MOD == 1);
    }
}
vector<pii> G[N];

void solve() {

    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) G[i].clear();

    matlen = 2*n;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back(pii(v, w));
        G[v].push_back(pii(u, w));
    }

    Mat base;
    auto a = base.a;
    for (int u = 1; u <= n; u++) {
        ll factor = inv[G[u].size()];
        for (auto e : G[u]) {
            int v = e.first, w = e.second;

            if (w == 1) {
                a[u+n][v] = factor;
                a[u][v+n] = factor;
            } else {
                a[u][v] = factor;
                a[u+n][v+n] = factor;
            }
        }
    }
    base = PowMod(base, k);
    printf("%lld\n", base.a[1][matlen]);
}

int main() {
    init();

    int T = 1;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}