#include<bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define inf 1010000000
#define infll 1010000000000000000ll
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define mpr make_pair
#define fi first
#define se second
#define pq priority_queue<int>
#define pqll priority_queue<ll>
#define up(x,y) (x<(y)?x=(y):0)
#define dn(x,y) (x>(y)?x=(y):0)
#define ad(x,y) (x=(x+(y))%mod)
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
#define N 109
#define mod 998244353
using namespace std;

int read(); ll readll();

int n, m, t, inv[N], deg[N], a[N][N][2], b[N][2], c[N][N][2];
int main(){
    int cas = read();
    int i; inv[0] = inv[1] = 1;
    for (i = 2; i < N; i++) inv[i] = mod - (ll)mod / i * inv[mod % i] % mod;
    while (cas--){
        scanf("%d%d%d", &n, &m, &t);
        memset(deg, 0, sizeof(deg));
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        int j, k, l;
        for (i = 1; i <= m; i++){
            int x = read(), y = read(), w = read();
            a[x][y][w]++; a[y][x][w]++; deg[x]++; deg[y]++;
        }
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                for (k = 0; k < 2; k++)
                    a[i][j][k] = (ll)a[i][j][k] * inv[deg[i]] % mod;
        b[1][0] = 1;
        for (; t; t >>= 1){
            if (t & 1){
                memset(c[0], 0, sizeof(c[0]));
                for (i = 1; i <= n; i++)
                    for (j = 1; j <= n; j++)
                        for (k = 0; k < 2; k++)
                            for (l = 0; l < 2; l++)
                                ad(c[0][j][k ^ l], (ll)b[i][k] * a[i][j][l]);
                memcpy(b, c[0], sizeof(c[0]));
            }
            memset(c, 0, sizeof(c));
            for (i = 1; i <= n; i++)
                for (j = 1; j <= n; j++)
                    for (k = 1; k <= n; k++)
                        for (int x = 0; x < 2; x++) for (int y = 0; y < 2; y++)
                            ad(c[i][k][x ^ y], (ll)a[i][j][x] * a[j][k][y]);
            memcpy(a, c, sizeof(c));
        }
        printf("%d\n", b[n][1]);
    }
    return 0;
}

int read(){
    int x=0; char ch=getchar(); bool flag=0;
    while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
    while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    return flag?-x:x;
}
ll readll(){
    ll x=0; char ch=getchar(); bool flag=0;
    while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
    while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    return flag?-x:x;
}