#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

constexpr int mod = 998244353;

inline int inv(int a) {
    a %= mod;
    if (a < 0) {
        a += mod;
    }
    int b = mod, u = 0, v = 1;
    while (a) {
        int t = b / a;
        b -= t * a;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    assert(b == 1);
    if (u < 0) {
        u += mod;
    }
    return u;
}

template <typename T>
vector<vector<T>> operator*(const vector<vector<T>>& a, const vector<vector<T>>& b) {
    vector<vector<T>> c((int) a.size(), vector<T>((int) b[0].size()));
    for (int i = 0; i < (int) c.size(); i++) {
        for (int k = 0; k < (int) b.size(); k++) {
            for (int j = 0; j < (int) c[0].size(); j++) {
                c[i][j] = (int) ((c[i][j] + 1LL * a[i][k] * b[k][j]) % mod);
            }
        }
    }
    return c;
}

template <typename T>
vector<vector<T>>& operator*=(vector<vector<T>>& a, const vector<vector<T>>& b) {
    return a = a * b;
}

template <typename T>
vector<vector<T>> power(vector<vector<T>> a, long long n) {
    vector<vector<T>> res(a.size(), vector<T>(a.size()));
    for (int i = 0; i < (int) a.size(); i++) {
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n & 1) {
            res *= a;
        }
        a *= a;
        n >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tt;
    cin >> tt;
    while (tt--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<vector<int>> a(2 * n, vector<int>(2 * n));
        for (int i = 0; i < m; i++) {
            int x, y, z;
            cin >> x >> y >> z;
            x--, y--;
            if (z == 0) {
                a[x][y] = a[y][x] = a[x + n][y + n] = a[y + n][x + n] = 1;
            } else {
                a[x][y + n] = a[x + n][y] = a[y][x + n] = a[y + n][x] = 1;
            }
        }
        for (int i = 0; i < 2 * n; i++) {
            int b = 0;
            for (int j = 0; j < 2 * n; j++) {
                b += a[i][j];
            }
            b = inv(b);
            for (int j = 0; j < 2 * n; j++) {
                if (a[i][j]) {
                    a[i][j] = b;
                }
            }
        }
        a = power(a, k);
        cout << a[0][2 * n - 1] << '\n';
    }
    return 0;
}