/*
 * Author: Kewth

 * Date:
  echo -n '  ' && date +%Y.%m.%d # Type "!!sh" in Vim.

 * Solution:
  To be updated after "Accept".

 * Digression:

 * CopyRight:
   __  __                  __   __
  |  |/  |.-----.--.--.--.|  |_|  |--.
  |     < |  -__|  |  |  ||   _|     |
  |__|\__||_____|________||____|__|__|

 */

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#pragma GCC optimize(2)

typedef long long ll;

static struct {
    inline operator int () { int x; return scanf("%d", &x), x; }
    /* inline operator ll () { ll x; return scanf("%lld", &x), x; } */
    /* template<class T> inline void operator () (T &x) { x = *this; } */
    /* template<class T, class ...A> inline void operator () (T &x, A &...a) */
    /* { x = *this; this -> operator () (a...); } */
} read;

const int maxn = 205, mod = 998244353;

inline ll power (ll x, int k) {
    if (k < 0) k += mod - 1;
    ll res = 1;
    while (k) {
        if (k & 1) (res *= x) %= mod;
        (x *= x) %= mod;
        k >>= 1;
    }
    return res;
}

int N = 0;
struct Matrix {
    ll x[maxn][maxn];
    Matrix (ll y = 0) {
        memset(x, 0, sizeof x);
        for (int i = 1; i <= N; i ++)
            x[i][i] = y;
        /* for (int i = 1; i <= N; i ++) */
        /*     for (int j = 1; j <= N; j ++) */
        /*         x[i][j] = i == j ? y : 0; */
    }
};

inline Matrix operator * (Matrix a, Matrix b) {
    Matrix c = 0;
    ll tmp = 1ll * mod * mod;
    for (int i = 1; i <= N; i ++)
        for (int j = 1; j <= N; j ++) {
            for (int k = 1; k <= N; k ++) {
                c.x[i][j] += a.x[i][k] * b.x[k][j];
                if (c.x[i][j] >= tmp) c.x[i][j] -= tmp;
            }
            c.x[i][j] %= mod;
        }
    return c;
}

struct Vector {
    ll x[maxn];
    inline ll & operator () (int i) { return x[i]; }
    Vector () { memset(x, 0, sizeof x); }
};

inline Vector operator * (Vector a, Matrix b) {
    Vector c;
    for (int j = 1; j <= N; j ++)
        for (int k = 1; k <= N; k ++)
            (c(j) += a(k) * b.x[k][j]) %= mod;
    return c;
}

int deg[maxn];

int main () {
    int T = read;
    while (T --) {
        Matrix M = 0;
        int n = read, m = read, k = read;
        N = n * 2;
        std::fill(deg, deg + n + 1, 0);
        for (int i = 1; i <= m; i ++) {
            int u = read, v = read, w = read;
            if (w == 0) {
                ++ M.x[u][v];
                ++ M.x[v][u];
                ++ M.x[n + u][n + v];
                ++ M.x[n + v][n + u];
            }
            if (w == 1) {
                ++ M.x[u][n + v];
                ++ M.x[n + v][u];
                ++ M.x[n + u][v];
                ++ M.x[v][n + u];
            }
            ++ deg[u], ++ deg[v];
        }
        for (int i = 1; i <= n; i ++) {
            ll x = power(deg[i], -1);
            for (int j = 1; j <= n * 2; j ++) {
                (M.x[i][j] *= x) %= mod;
                (M.x[n + i][j] *= x) %= mod;
            }
        }
        Vector V;
        V.x[1] = 1;
        while (k) {
            if (k & 1) V = V * M;
            M = M * M;
            k >>= 1;
        }
        printf("%lld\n", V.x[n * 2]);
    }
}