#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

//#include <atcoder/convolution>
//#include <atcoder/modint> 
//using Modint = atcoder::modint998244353;

using namespace std;
typedef long long ll;

void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    ex_gcd(b, a % b, d, y, x);
    y -= a / b * x;
  }
}
ll inv(ll a, ll n) {
  ll d, x, y;
  ex_gcd(a, n, d, x, y);
  return d == 1 ? (x % n + n) % (n / d) : -1;
}
ll gcd(ll x, ll y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}

int gcd(int x, int y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}

inline void scan_d(int &ret) {
    char c; ret=0;
    while((c=getchar())<'0'||c>'9');
    while(c>='0'&&c<='9') ret=ret*10+(c-'0'),c=getchar();
}

const int maxn = 105;
const int mod = 998244353;

// https://www.kancloud.cn/digest/acarthur/166627
typedef vector<ll> vec;
typedef vector<vec> mat;
mat mul(mat &a, mat &b) {
    int n = a.size();
    int m = a[0].size();
    int mm = b[0].size();
    mat c(n, vec(mm));
    for(int i=0;i<n;i++) {
   for(int k=0;k<m;k++) {
      for(int j=0;j<mm;j++) {
          c[i][j] = (c[i][j] + a[i][k] * b[k][j])%mod;
          }
        }
    }
    return c;
}
mat pow(mat a, int k) {
    int n = a.size();
    mat b(n, vec(n));
    for(int i=0;i<n;i++) {
        b[i][i] = 1;
    }
    while(k > 0) {
        if(k & 1) b = mul(b, a);
        a = mul(a, a);
        k >>= 1;
    }
    return b;
}

int e[maxn][maxn];

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.cpp", "r", stdin);
  freopen("/Users/suiyuan2009/CLionProjects/icpc/output.cpp", "w", stdout);
#endif
  int T;
  scan_d(T);
  while(T--){
    int n,m,K;
    scan_d(n);
    scan_d(m);
    scan_d(K);
    memset(e, -1, sizeof(e));
    for(int i=0;i<m;i++){
      int x,y,z;
      scan_d(x);
      scan_d(y);
      scan_d(z);
      e[x][y] = e[y][x] = z;
    }
    mat tt(n + n, vec(n + n));
    for(int i=1;i<=n;i++){
      int cnt = 0;
      for(int j=1;j<=n;j++)if(e[i][j]!=-1)cnt++;
      if(cnt==0)continue;
      ll val = inv(cnt, mod);
      for(int j=1;j<=n;j++){
        int tmp = e[i][j];
        if(tmp==-1)continue;
        if(tmp==0){
          tt[j-1][i-1] = val;
          tt[j+n-1][i+n-1] = val;
        } else {
          tt[j-1][i+n-1] = val;
          tt[j+n-1][i-1] = val;
        }
      }
    }
    mat mm = pow(tt, K);
    mat ret(n+n, vec(1));
    ret[0][0] = 1;
    mat ans = mul(mm, ret);
    printf("%d\n", int(ans[n+n-1][0]));
  }
  return 0;
}