#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N=205;
const int MOD=998244353;
int add (int x,int y)   {x=x+y;return x>=MOD?x-MOD:x;}
int mul (int x,int y)   {return (LL)x*y%MOD;}
int dec (int x,int y)   {x=x-y;return x<0?x+MOD:x;}
int Pow (int x,int y)
{
    if (y==1) return x;
    int lalal=Pow(x,y>>1);
    lalal=mul(lalal,lalal);
    if (y&1) lalal=mul(lalal,x);
    return lalal;
}
struct qt
{
    int x,y;
    int f[N][N];
    friend qt operator * (qt a,qt b)
    {
        qt c;c.x=a.x;c.y=b.y;
        memset(c.f,0,sizeof(c.f));
       
        for (int u=1;u<=a.x;u++)
        for (int i=1;i<=b.y;i++)
        for (int j=1;j<=a.y;j++) 
        c.f[u][i]=add(c.f[u][i],mul(a.f[u][j],b.f[j][i]));
        return c;
    }
    void clear ()
    {
        for (int u=1;u<=x;u++)
        for (int i=1;i<=y;i++)
        f[u][i]=0;
    }
}A,B;
qt ksm (qt x,int y)
{
    qt ans;ans.x=x.x;ans.y=x.y;
    ans.clear();
    for(int i=1;i<=ans.x;i++) ans.f[i][i]=1;
    while(y)
    {
        //printf("%d\n",y);
        if(y&1) ans=ans*x;
        x=x*x;y>>=1;
    }
    return ans;
}
int w[N][N],d[N];
int n,m,k;
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for (int u=1;u<=n;u++)
        {
            for (int i=1;i<=n;i++)    w[u][i]=-1;
            d[u]=0;
        }
        for (int u=1;u<=m;u++)
        {
            int x,y,ww;
            scanf("%d%d%d",&x,&y,&ww);
            w[x][y]=ww;w[y][x]=ww;
            d[x]++;d[y]++;
        }
        B.clear();
        B.x=2*n;B.y=2*n;
        for (int u=1;u<=n;u++)
        {
            int o=Pow(d[u],MOD-2);
            for (int i=1;i<=n;i++)
            {
                if (w[u][i]==0)
                {
                    B.f[u][i]=o;
                    B.f[u+n][i+n]=o;
                }
                if (w[u][i]==1)
                {
                    B.f[u+n][i]=o;
                    B.f[u][i+n]=o;
                }
            }
        }
        //printf("YES\n");
        A.clear();
        A.x=1;A.y=2*n;
        A.f[1][1]=1;
        B=ksm(B,k);
        
        A=A*B;
        printf("%d\n",A.f[1][2*n]);
    }
    return 0;
}