#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ud unsigned int
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x3f
#define MAX_INF_VAL 0x3f3f3f3f
#define MAX_INF_VAL_LL 0x3f3f3f3f3f3f3f3f
//#define pi 3.141592653589
#define eps 1e-9
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
//#define p 2173412051LL
//#define sz 2

using namespace std;

template< typename T > void read( T &x ) {
    x = 0;
    char ch = getchar();
    ll f = 1;
    while( !isdigit( ch ) ) {
        if( ch == '-' )
        f *= -1;
        ch = getchar();
    }
    while( isdigit( ch ) ) {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}

struct custom_hash {
    static uint64_t splitmix64( uint64_t x ) {
        x += 0x9e3779b97f4a7c15;
        x = ( x ^ ( x >> 30 ) ) * 0xbf58476d1ce4e5b9;
        x = ( x ^ ( x >> 27 ) ) * 0x94d049bb133111eb;
        return x ^ ( x >> 31 );
    }

    size_t operator() ( uint64_t x ) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64( x + FIXED_RANDOM );
    }
};

const ll p = 998244353;
#define sz 200

struct matrix {
    ll a[ sz ][ sz ];
    void init() {
        memset( a, 0, sizeof( a ) );
        for( int i = 0; i < sz; ++i )
            a[ i ][ i ] = 1;
    }
    void clear() {
        memset( a, 0, sizeof( a ) );
    }
};

matrix matrix_pow( matrix, ll );
matrix matrix_mul( matrix, matrix );
ll pow_mod( ll, ll );

int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 ), cout.tie( 0 );
    int t;
    cin >> t;
    while( t-- ) {
        int n, m, k;
        cin >> n >> m >> k;
        matrix a;
        a.clear();
        vector< vector< pair< int, int > > > e( n );
        while( m-- ) {
            int x, y, z;
            cin >> x >> y >> z;
            --x;
            --y;
            e[ x ].push_back( { y, z } );
            e[ y ].push_back( { x, z } );
        }
        for( int i = 0; i < n; ++i ) {
            ll vl = pow_mod( e[ i ].size(), p - 2 );
            for( auto fk: e[ i ] ) {
                auto v = fk.first;
                auto w = fk.second;
                if( w == 1 ) {
                    a.a[ v + n ][ i ] = vl;
                    a.a[ v ][ i + n ] = vl;
                } else {
                    a.a[ v ][ i ] = vl;
                    a.a[ v + n ][ i + n ] = vl;
                }
            }
        }
        a = matrix_pow( a, k );
        cout << a.a[ 2 * n - 1 ][ 0 ] << '\n';
    }
    return 0;
}


matrix matrix_pow( matrix x, ll n ) {
    matrix tmp;
    tmp.init();
    while( n ) {
        if( n & 1 )
            tmp = matrix_mul( tmp, x );
        x = matrix_mul( x, x );
        n >>= 1;
    }
    return tmp;
}

matrix matrix_mul( matrix a, matrix b ) {
    matrix ans;
    ans.clear();
    for( int i = 0; i < sz; ++i )
        for( int j = 0; j < sz; ++j )
            for( int k = 0; k < sz; ++k )
                ans.a[ i ][ j ] += a.a[ i ][ k ] * b.a[ k ][ j ] % p;
    for( int i = 0; i < sz; ++i )
        for( int j = 0; j < sz; ++j )
            ans.a[ i ][ j ] %= p;
    return ans;
}

ll pow_mod( ll x, ll y ) {
    ll res = 1;
    while( y ) {
        if( y & 1 )
            res = res * x % p;
        x = x * x % p;
        y >>= 1;
    }
    return res;
}