#include <bits/stdc++.h>

using namespace std;
#define MOD 998244353

struct matrix {
  unsigned long long A[201][201];
  unsigned long long* operator[] (int x) { return A[x]; }

  void clear() { memset(A, 0, sizeof(A)); }
  matrix() { clear(); }

  matrix operator* (matrix B) {
    matrix C;
    for (int i = 1; i <= 200; ++i)
      for (int j = 1; j <= 200; ++j)
        for (int t = 0; t < 20; ++t) {
          for (int k = t * 10 + 1; k <= t * 10 + 10; ++k)
            C[i][j] = C[i][j] + A[i][k] * B[k][j];
          C[i][j] %= MOD;
        }
    return C;
  }
};
matrix A;
int T, n, m, k, u, v, w, deg[101];

long long power(long long x, int y) {
  long long ans = 1;
  while (y) {
    if (y & 1) ans = ans * x % MOD;
    x = x * x % MOD;
    y /= 2;
  }
  return ans;
}

matrix power(matrix A, int x) {
  matrix ans;
  for (int i = 1; i <= 200; ++i) ans[i][i] = 1;
  while (x) {
    if (x & 1) ans = ans * A;
    A = A * A;
    x /= 2;
  }
  return ans;
}

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &n, &m, &k);
    A.clear();
    memset(deg, 0, sizeof(deg));
    while (m--) {
      scanf("%d%d%d", &u, &v, &w);
      ++deg[u];
      ++deg[v];
      if (w)
        A[u][v + n] = A[u + n][v] = A[v][u + n] = A[v + n][u] = 1; else
        A[u][v] = A[u + n][v + n] = A[v][u] = A[v + n][u + n] = 1;
    }
    for (int i = 1; i <= 2 * n; ++i) {
      int tmp = power(deg[i > n ? i - n : i], MOD - 2);
      for (int j = 1; j <= 2 * n; ++j)
        if (A[i][j])
          A[i][j] = tmp;
    }
    A = power(A, k);
    printf("%d\n", A[1][2 * n]);
  }
  return 0;
}