#include <bits/stdc++.h>

typedef long long LL;

#define FOR(i, a, b) for (int i = (a), i##_END_ = (b); i <= i##_END_; ++i)
#define DNF(i, a, b) for (int i = (a), i##_END_ = (b); i >= i##_END_; --i)

template <typename Tp> void in(Tp &x) {
  char ch = getchar(), f = 1; x = 0;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= f;
}

template <typename Tp> bool chkmax(Tp &x, Tp y) {return x >= y ? 0 : (x=y, 1);}
template <typename Tp> bool chkmin(Tp &x, Tp y) {return x <= y ? 0 : (x=y, 1);}
template <typename Tp> Tp Max(const Tp &x, const Tp &y) {return x > y ? x : y;}
template <typename Tp> Tp Min(const Tp &x, const Tp &y) {return x < y ? x : y;}

const int MAXN = 210;
const int MOD = 998244353;

int T, n, m, K, G[MAXN][MAXN], mat[MAXN][MAXN], ret[MAXN][MAXN];

int power(int x, int y) {
  int ret = 1;
  while (y) {
    if (y & 1) ret = 1ll * x * ret % MOD;
    x = 1ll * x * x % MOD;
    y >>= 1;
  }
  return ret;
}

int id(int x, int y) {return x + y * n;}

void mul(int A[MAXN][MAXN], int B[MAXN][MAXN], int C[MAXN][MAXN]) {
  static int tmp[MAXN][MAXN];
  FOR(i, 1, 2 * n) FOR(j, 1, 2 * n) tmp[i][j] = 0;
  FOR(i, 1, 2 * n) FOR(k, 1, 2 * n) {
    int x = A[i][k];
    FOR(j, 1, 2 * n)
      tmp[i][j] = (tmp[i][j] + 1ll * x * B[k][j] % MOD) % MOD;
  }
  FOR(i, 1, 2 * n) FOR(j, 1, 2 * n) C[i][j] = tmp[i][j];
}

void solve() {
  in(n); in(m); in(K);
  FOR(i, 1, 2 * n) FOR(j, 1, 2 * n) G[i][j] = -1, mat[i][j] = 0;
  FOR(i, 1, m) {int x, y, w; in(x); in(y); in(w); G[x][y] = G[y][x] = w;}
  FOR(i, 1, n) {
    int tot = 0;
    FOR(j, 1, n) if (G[i][j] != -1) ++tot;
    int p = power(tot, MOD - 2);
    FOR(j, 1, n) if (G[i][j] != -1) {
      FOR(t, 0, 1) {
        int nxt = id(j, (t ^ G[i][j]));
        int now = id(i, t);
        mat[nxt][now] = p;
      }
    }
  }
  FOR(i, 1, 2 * n) FOR(j, 1, 2 * n) ret[i][j] = 0;
  FOR(i, 1, 2 * n) ret[i][i] = 1;
  while (K) {
    if (K & 1) mul(ret, mat, ret);
    mul(mat, mat, mat);
    K >>= 1;
  }
  int fir = id(1, 0);
  printf("%d\n", ret[id(n, 1)][fir]);
}

int main() {
  in(T); while (T--) solve();
  return 0;
}