// Skyqwq
#include <bits/stdc++.h>
#define rint register int
#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long LL;

template <typename T> void chkMax(T &x, T y) { if (y > x) x = y; }
template <typename T> void chkMin(T &x, T y) { if (y < x) x = y; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 205, P = 998244353;

typedef pair<int, int> PII;

int n, m, k, d[N];
 
vector<PII> g[N];


int inline power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (LL)res * a % P;
        a = (LL)a * a % P;
        b >>= 1;
    }
    return res;
}

struct Mat{
    LL w[N][N];
    int n, m;
    Mat inline operator * (const Mat &b) const {
        Mat c; 
        c.n = n, c.m = b.m;
        for (rint i = 1; i <= n; i++) {
            for (rint j = 1; j <= b.m; j++) {
                c.w[i][j] = 0;
                for (rint k = 1; k <= m; k++) {
                    c.w[i][j] += w[i][k] * b.w[k][j];
                    if (c.w[i][j] > 8e18) c.w[i][j] %= P;
                }
                c.w[i][j] %= P;
            }
        }
        return c;
    }
} res, A;


void inline clear() {
    for (int i = 1; i <= n; i++) g[i].clear(), d[i] = 0;
    memset(A.w, 0, sizeof A.w);
    memset(res.w, 0, sizeof res.w);
}

void inline add(LL &x, int y) {
    x += y;
    if (x >= P) x -= P;
}
int main() {
    int T; read(T);
    while (T--) {
        read(n), read(m), read(k);
        while (m--) {
            int u, v, w; read(u), read(v), read(w);
            g[u].pb(mp(v, w));
            g[v].pb(mp(u, w));
        }

        res.n = 1, res.m = A.n = A.m = 2 * n;
        res.w[1][1] = 1;
        for (int u = 1; u <= n; u++) {
            int p = power(g[u].size(), P - 2);
            for (PII t: g[u]) {
                int v = t.fi, w = t.se;
                if (w) {
                    add(A.w[u][v + n], p);
                    add(A.w[u + n][v], p);
                } else {
                    add(A.w[u + n][v + n], p);
                    add(A.w[u][v], p);
                }
            }
        }
        int b = k;
        while (b) {
            if (b & 1) res = res * A;
            A = A * A;
            b >>= 1;
        }
        printf("%lld\n", res.w[1][2 * n]);
        clear();
    }
    return 0;
}