#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxl=3e5+10;
const int mod=998244353;

int n,m,k,cnt,tot,cas;ll ans;
int a[maxl],b[maxl],deg[maxl];
char s[maxl];
struct ed{int v,w;};
vector<ed> e[maxl];

inline void add(ll &a,ll b)
{
    a=(a+b);
    if(a>=mod) a-=mod;
}

struct matrix
{
    ll a[210][210];
    matrix()
    {
        memset(a,0,sizeof(a));
    }
    inline void clear()
    {
        memset(a,0,sizeof(a));
    }
    matrix operator * (const matrix &b)const
    {
        matrix c;
        for(int i=1;i<=2*n;i++)
            for(int j=1;j<=2*n;j++)
                for(int k=1;k<=2*n;k++)
                    c.a[i][k]=(c.a[i][k]+a[i][j]*b.a[j][k])%mod;
        return c;
    }
};

inline matrix qp(matrix a,ll b)
{
    matrix ans,cnt=a;
    for(int i=1;i<=n;i++) ans.a[i][i]=1;
    while(b)
    {
        if(b&1)
            ans=ans*cnt;
        cnt=cnt*cnt;
        b>>=1;
    }
    return ans;
}

inline ll qp(ll a,ll b)
{
    ll ans=1,cnt=a;
    while(b)
    {
        if(b&1)
            ans=ans*cnt%mod;
        cnt=cnt*cnt%mod;
        b>>=1;
    }
    return ans;
}

inline void prework()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        e[i].clear(),deg[i]=0;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        e[u].push_back(ed{v,w});
        e[v].push_back(ed{u,w});
        ++deg[u];++deg[v];
    }
}

inline void mainwork()
{
    matrix c;
    for(int i=1;i<=n;i++)
    {
        for(ed ee:e[i])
        if(ee.w)
        {
            c.a[i][ee.v+n]=qp(deg[i],mod-2);
            c.a[i+n][ee.v]=qp(deg[i],mod-2);
        }
        else
        {
            c.a[i][ee.v]=qp(deg[i],mod-2);
            c.a[i+n][ee.v+n]=qp(deg[i],mod-2);
        }
    }
    c=qp(c,k);
    ans=c.a[1][2*n];
}

inline void print()
{
    printf("%lld\n",ans);
}

int main()
{
    int t=1;
    scanf("%d",&t);
    for(cas=1;cas<=t;cas++)
    {
        prework();
        mainwork();
        print();
    }
    return 0;
}