#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <queue>
 
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define mset(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
 
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
 
using namespace std;
typedef long long ll;
 
#ifdef local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() {
    cout << endl;
}
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) {
    for (auto x: a)
        cout << x << ' ';
    err(args...);
}
template<typename T, typename... Args>
void err(T a, Args... args) {
    cout << a << ' ';
    err(args...);
}
#else
#define dbg(...)
#endif
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int mod=998244353;
const int N = 400+5;
const int M = N*100;
const int maxn=1e7+50;

typedef vector<ll> vec;
typedef vector<vec> mat;
mat mul(mat& A, mat& B)
{
    mat C(A.size(), vec(B[0].size()));
    for (int i = 0; i < A.size(); i++)
        for (int k = 0; k < B.size(); k++)
            if (A[i][k])
                for (int j = 0; j < B[0].size(); j++)
                    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
    return C;
}
mat Pow(mat A, ll n)
{
    mat B(A.size(), vec(A.size()));
    for (int i = 0; i < A.size(); i++) B[i][i] = 1;
    for (; n; n >>= 1, A = mul(A, A))
        if (n & 1) B = mul(B, A);
    return B;
}

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

ll inv(ll a) {
    return qpow(a,mod-2);
}

ll du[N];

struct E {
    int u, v, w;
    E(int _u, int _v, int _w) : u(_u), v(_v), w(_w) {
        
    }
};

vector<E> edges;

void work() {
    int n, m, k;
    cin >> n >> m >> k;
    edges.clear();
    mat startMat;
    mat edgeMat;
    for (int i = 0; i < (n<<1); ++i) {
        du[i] = 0;
        vec a;
        edgeMat.push_back(a);
        startMat.push_back(a);
        for (int j = 0; j < (n<<1); ++j) {
            edgeMat[i].emplace_back(0);
            startMat[i].emplace_back(0);
        }
    }
    startMat[0][0] = 1;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        ++du[u];
        ++du[v];
        edges.emplace_back(u,v,w);
    }
    for (int i = 0; i < m; ++i) {
        auto &e = edges[i];
        auto &u = e.u;
        auto &v = e.v;
        auto &w = e.w;
        
        ll invu = inv(du[u]);
        ll invv = inv(du[v]);
        
//        dbg(u,v,w,invu,invv);
        edgeMat[(u<<1)][(v<<1)^w] = invu;
        edgeMat[(u<<1)^1][(v<<1)^1^w] = invu;
        
        edgeMat[(v<<1)][(u<<1)^w] = invv;
        edgeMat[(v<<1)^1][(u<<1)^1^w] = invv;
    }
    
    
//    cout << "\n";
//    for (auto &v : edgeMat) {
//        for (auto &x : v) {
//            cout << x << " ";
//        }
//        cout << "\n";
//    }
    
    
    
    mat edgeMatPow = Pow(edgeMat, k);
    
    
//    cout << "\n";
//    for (auto &v : edgeMatPow) {
//        for (auto &x : v) {
//            cout << x << " ";
//        }
//        cout << "\n";
//    }
    
    
    mat ans = mul(startMat, edgeMatPow);
    
//    cout << "\n";
//    for (auto &v : ans) {
//        for (auto &x : v) {
//            cout << x << " ";
//        }
//        cout << "\n";
//    }
    
    cout << ans[0][((n-1)<<1)^1] << "\n";
}
 
int main() {
#ifdef local
    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
#endif // local
    IOS;
//    init();
     int t;
     cin>>t;
     while(t--)
        work();
    return 0;
}