#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;

typedef long long ll;

const int N = 2e2 + 10;
const int MOD = 998244353;

int add(int a, int b) { return a + b >= MOD ? a + b - MOD : a + b; }
int mul(int a, int b) { return 1LL * a * b % MOD; }
int qpow(int x, int n) {
    int res = 1;
    while (n > 0) {
        if (n & 1) res = mul(res, x);
        x = mul(x, x); n /= 2;
    }
    return res;
}

int n, m; ll k;
int res[N][N], co[N][N], fu[N][N];

bool check(int x) {
    return 1 <= x && x <= 2 * n;
}

void calrc() {
    for (int i = 1; i <= 2 * n; i++) {
        if (!check(i)) continue;
        for (int j = 1; j <= 2 * n; j++) {
            if (!check(j)) continue;
            for (int k = 1; k <= 2 * n; k++) {
                if (!check(k)) continue;
                fu[i][j] = add(fu[i][j], mul(res[i][k], co[k][j]));
            }
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * n; j++) {
            res[i][j] = fu[i][j]; fu[i][j] = 0;
        }
    }
}

void calcc() {
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * n; j++) {
            for (int k = 1; k <= 2 * n; k++) {
                fu[i][j] = add(fu[i][j], mul(co[i][k], co[k][j]));
            }
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        for (int j = 1; j <= 2 * n; j++) {
            co[i][j] = fu[i][j]; fu[i][j] = 0;
        }
    }
}

void solve(ll k) {
    memset(res, 0, sizeof(res));
    for (int i = 1; i <= 2 * n; i++) res[i][i] = 1;
    while (k > 0) {
        if (k & 1) calrc();
        calcc(); 
        k /= 2;
    }
}

int cnt[N];

int main() {
    //freopen("0.txt", "r", stdin);
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d%lld", &n, &m, &k);
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            cnt[a]++; cnt[b]++;
            if (c == 0) {
                co[a][b]++;
                co[a + n][b + n]++;
                swap(a, b);
                co[a][b]++;
                co[a + n][b + n]++;
            }
            else {
                co[a + n][b]++;
                co[a][b + n]++;
                swap(a, b);
                co[a + n][b]++;
                co[a][b + n]++;
            }
        }
        for (int u = 1; u <= 2 * n; u++) {
            int r = qpow(cnt[u], MOD - 2);
            if (u > n) r = qpow(cnt[u - n], MOD - 2);
            for (int v = 1; v <= 2 * n; v++) co[u][v] = mul(co[u][v], r);
        }
        solve(k);
        printf("%d\n", res[1][2 * n]);
        memset(cnt, 0, sizeof(cnt));
        memset(co, 0, sizeof(co));
    }
    return 0;
}