#include <bits/stdc++.h>
using namespace std;

const int P = 998244353;
int T, n, m, k, deg[205], a[205][205], inv[205], ans[205][205];
vector<tuple<int, int, int>> g;

void multiply(int a[205][205], int b[205][205], int c[205][205]) {
  static int d[205][205];
  for (int i = 1; i <= 2 * n; ++i)
    for (int j = 1; j <= 2 * n; ++j)
      d[i][j] = 0;
  for (int i = 1; i <= 2 * n; ++i)
    for (int k = 1; k <= 2 * n; ++k)
      for (int j = 1; j <= 2 * n; ++j)
        d[i][j] = (d[i][j] + 1ll * a[i][k] * b[k][j]) % P;
  memcpy(c, d, sizeof d);
}

int main() {
  scanf("%d", &T);
  inv[1] = 1;
  for (int i = 2; i <= 100; ++i) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
  while (T--) {
    scanf("%d%d%d", &n, &m, &k);
    g.clear();
    for (int i = 1; i <= n; ++i) deg[i] = 0;
    memset(a, 0, sizeof a);
    memset(ans, 0, sizeof ans);
    for (int i = 1; i <= 2 * n; ++i) ans[i][i] = 1;
    for (int i = 1; i <= m; ++i) {
      int u, v, w;
      scanf("%d%d%d", &u, &v, &w);
      g.emplace_back(u, v, w);
      deg[u]++, deg[v]++;
    }
    for (auto p : g) {
      int u = get<0>(p), v = get<1>(p);
      if (get<2>(p)) {
        a[2 * u - 1][2 * v] = inv[deg[u]];
        a[2 * u][2 * v - 1] = inv[deg[u]];
        a[2 * v - 1][2 * u] = inv[deg[v]];
        a[2 * v][2 * u - 1] = inv[deg[v]];
      } else {
        a[2 * u][2 * v] = inv[deg[u]];
        a[2 * u - 1][2 * v - 1] = inv[deg[u]];
        a[2 * v][2 * u] = inv[deg[v]];
        a[2 * v - 1][2 * u - 1] = inv[deg[v]];
      }
    }
    for (; k; k >>= 1, multiply(a, a, a))
      if (k & 1) multiply(ans, a, ans);
    printf("%d\n", ans[1][2 * n]);
  }
}