#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;
typedef double db;
typedef long double ldb;
typedef vector <int> vi;
typedef vector <ll> vl;
struct pii { int x,y; };
struct pll { ll  x,y; };
typedef vector <pii> vii;
typedef vector <pll> vll;
#define pb push_back
const ll MOD = 998244353;
const int N = 102;
inline int lowbit(int x) {return x&(-x);}
ll getgcd(ll x,ll y) {return (y==0) ? x : getgcd(y,x%y);}
ll power(ll x,ll mi,ll mod = MOD)
{
    ll s1=1LL,s2=x%mod,m=mi;
    for (;m;m>>=1) {if (m&1) s1=s1*s2%mod;s2=s2*s2%mod;}
    return s1;
}
inline ll getinv(ll x,ll mod = MOD) {return power(x,mod - 2);};
int inv[N];
int a[N][N],d[N];
int n,m,K;
struct Matrix
{
    pii x[N][N];
    friend Matrix operator * (const Matrix & a,const Matrix & b)
    {
        Matrix c;
        for (int i=1;i<=n;++i)
        {
            for (int j=1;j<=n;++j)
            {
                c.x[i][j]={0,0};
                for (int k=1;k<=n;++k)
                {
                    (c.x[i][j].x+=(1LL*a.x[i][k].x*b.x[k][j].x+1LL*a.x[i][k].y*b.x[k][j].y)%MOD)%=MOD;
                    (c.x[i][j].y+=(1LL*a.x[i][k].x*b.x[k][j].y+1LL*a.x[i][k].y*b.x[k][j].x)%MOD)%=MOD;
                }
            }
        }
        return c;
    }
}mat,res;
Matrix power(const Matrix & x,int mi)
{
    Matrix s1 , s2 = x;
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        {
            s1.x[i][j]= ((i==j) ? (pii){1,0} : (pii){0,0});
        }
    }
    while (mi)
    {
        if (mi&1) s1=s1*s2;
        mi>>=1;
        s2=s2*s2;
    }
    return s1;
}
void init()
{
    scanf("%d%d%d",&n,&m,&K);
    for (int i=1;i<=n;++i)
    {
        d[i]=0;
        for (int j=1;j<=n;++j)
        {
            a[i][j]=-1;
            mat.x[i][j]={0,0};
        }
    }
    for (int i=1;i<=m;++i)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        a[u][v]=a[v][u]=w;
        ++d[u];++d[v];
    }
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        if (a[i][j]>=0)
        {
            if (a[i][j]) mat.x[i][j]={0,inv[d[j]]};
            else mat.x[i][j]={inv[d[j]],0};
        }
    }
    res=power(mat,K);
    ll ans = 0;
    ans=(res.x[n][1].y%MOD+MOD)%MOD;
    cout<<ans<<"\n";
    return;
}
void solve()
{
    return;
}
int main()
{
    for (int i=N-1;i>=0;--i) inv[i]=getinv(i);
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    for (int cas=1;cas<=T;++cas)
    {
        //printf("Case %d : \n",cas);
        init();
        solve();
    }
    return 0;
}