#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
const int maxn = 500010, inf = 1e9 + 233, mod = 998244353;

int f[21][110][110][2], g[110][110][2], ans[110][110][2];
int mp[110][110], deg[110];
int n, m, K, x, y;

template <typename T>
inline void read(T &k)
{
    int f = 1; k = 0; char c = getchar();
    while (c < '0' || c > '9') c == '-' && (f = -1), c = getchar();
    while (c <= '9' && c >= '0') k = k * 10 + c - '0', c = getchar();
    k *= f;
}

int power(int a, int b)
{
    int ans = 1;
    for (; b; b >>= 1, a = 1ll * a * a % mod)
        if (b & 1)
            ans = 1ll * ans * a % mod;
    return ans;
}

void solve()
{
    read(n); read(m); read(K);
    memset(mp, -1, sizeof(mp));
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(deg, 0, sizeof(deg));

    for (int i = 1; i <= m; i++)
    {
        read(x); read(y); 
        read(mp[x][y]);
        mp[y][x] = mp[x][y];
        deg[x]++; deg[y]++;
    }

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        if (~mp[i][j])
            f[0][i][j][mp[i][j]] = power(deg[i], mod - 2);


    for (int t = 1; t <= 20; t++)
    {
        for (int k = 1; k <= n; k++)
        {
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    for (int s1 = 0; s1 < 2; s1++)
                    {
                        for (int s2 = 0; s2 < 2; s2++)
                            f[t][i][j][s1 ^ s2] = (f[t][i][j][s1 ^ s2] + 1ll * f[t - 1][i][k][s1] * f[t - 1][k][j][s2]) % mod;
                    }
                }
            }
        }
    }

    for (int i = 1; i <= n; i++)
        g[i][i][0] = 1;
    for (int t = 0; t <= 20; t++)
    if (K & (1 << t))
    {
        memset(ans, 0, sizeof(ans));

        for (int k = 1; k <= n; k++)
        {
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    for (int s1 = 0; s1 < 2; s1++)
                    {
                        for (int s2 = 0; s2 < 2; s2++)
                            ans[i][j][s1 ^ s2] = (ans[i][j][s1 ^ s2] + 1ll * g[i][k][s1] * f[t][k][j][s2]) % mod;
                    }
                }
            }
        }

        swap(ans, g);
    }

    printf("%d\n", g[1][n][1]);
}

int main()
{
    int T;
    read(T);
    while (T--)
        solve();
}