#include <bits/stdc++.h>
using namespace std;
const int maxn = 200, mod = 998244353;
int T;
int n, m, k;
int N, M;
struct edge {
    int to, w;
};
vector<edge> g[maxn + 10];
int id[maxn + 10][2];

struct mat {
    int a[maxn + 1][maxn + 1];
}a;

mat operator * (const mat &a, const mat &b) {
    mat ans;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j) {
            ans.a[i][j] = 0;
            unsigned long long x, y = 0;
            for (int k = 1; k <= N; k += 16) {
                x = 0;
                for (int l = k; l <= N && l < k + 16; ++l)
                    if (a.a[i][l])
                        x += 1ll * a.a[i][l] * b.a[l][j];
                y += x % mod;
            }
            ans.a[i][j] = y % mod;
        }
    return ans;
}

mat fpow(mat x, int y) {
    mat ans = x; --y;
    while (y) {
        if (y & 1) ans = ans * x;
        y >>= 1; x = x * x;
    }
    return ans;
}

int fpow(int x, int y = mod - 2) {
    int ans = 1;
    while (y) {
        if (y & 1) ans = 1ll * ans * x % mod;
        y >>= 1; x = 1ll * x * x % mod;
    }
    return ans;
}


int main() {
    scanf("%d", &T);
//    T = 10;
    while (T--) {
        scanf("%d%d%d", &n, &m, &k);
//        n = 100; m = n * n; k = 1 << 19;
        for (int i = 1; i <= n; ++i) g[i].clear();
        for (int i = 1; i <= m; ++i) {
            int l, r, w; scanf("%d%d%d", &l, &r, &w);
        //    l = rand() % n + 1; r = rand() % n + 1; w = rand() % 2;
            g[l].push_back((edge){r, w});
            g[r].push_back((edge){l, w});
        }
        N = 0;
        for (int i = 1; i <= n; ++i) {
            id[i][0] = ++N;
            id[i][1] = ++N;
        }
        memset(a.a, 0,sizeof a.a);
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < 2; ++j) {
                int p = id[i][j];
                int w = fpow(g[i].size());
                for (int k = 0; k < (int)g[i].size(); ++k) {
                    edge e = g[i][k];
                    a.a[p][id[e.to][j ^ e.w]] = w;
                }
            }
        a = fpow(a, k);
        printf("%d\n", a.a[id[1][0]][id[n][1]]);
    }
}