#include <cstdio>
#include <cctype>
#include <cstring>
typedef long long ll;
void Read(int &x){
    char c;
    while(!isdigit(c=getchar()));
    x=(c&15);
    while(isdigit(c=getchar()))
        x=x*10+(c&15);
}
void Print(int x,char c){
    int i;
    for(i=1;i*10LL<=x;i*=10);
    for(;i;i/=10)
        putchar(x/i%10|48);
    putchar(c);
}
const int P=998244353,N=205;
int mpower(ll a,int b){
    int s=1;
    while(b){
        if(b&1)
            s=s*a%P;
        a=a*a%P;
        b>>=1;
    }
    return s;
}
int T,n,siz,m,k,d[N],res[N<<1],t[N<<1],u[N*N],v[N*N],w[N*N];
struct Mat{
    int a[N][N];
}a;
Mat operator*(const Mat &a,const Mat &b){
    static Mat c;
    for(int i=1;i<=siz;++i)
        for(int j=1;j<=siz;++j){
            int s=0,k;
            #define par(u) +(ll)a.a[i][k+u]*b.a[k+u][j]
            for(k=1;k+7<=siz;k+=8)
                s=(s par(0)par(1)par(2)par(3)par(4)par(5)par(6)par(7))%P;
            #undef par
            for(;k<=siz;++k)
                s=(s+(ll)a.a[i][k]*b.a[k][j])%P;
            c.a[i][j]=s;
        }
    return c;
}
void uto(const Mat &a){
    for(int i=1;i<=siz;++i){
        int s=0;
        for(int k=1;k<=siz;++k)
            s=(s+(ll)a.a[i][k]*res[k])%P;
        t[i]=s;
    }
    memcpy(res+1,t+1,n<<3);
}
int main(){
    Read(T);
    while(T--){
        Read(n),Read(m),Read(k);
        siz=n<<1;
        memset(d+1,0,n<<2);
        memset(res+1,0,n<<3);
        res[1]=1;
        for(int i=1;i<=siz;++i)
            for(int j=1;j<=siz;++j)
                a.a[i][j]=0;
        for(int i=0;i<m;++i){
            Read(u[i]),Read(v[i]),Read(w[i]);
            ++d[u[i]],++d[v[i]];
        }
        for(int i=1;i<=n;++i)
            d[i]=mpower(d[i],P-2);
        for(int i=0;i<m;++i){
            a.a[u[i]][v[i]+w[i]*n]=a.a[u[i]+n][v[i]+(w[i]^1)*n]=d[v[i]];
            a.a[v[i]][u[i]+w[i]*n]=a.a[v[i]+n][u[i]+(w[i]^1)*n]=d[u[i]];
        }
        while(k){
            if(k&1)
                uto(a);
            a=a*a;
            k>>=1;
        }
        Print(res[n<<1],10);
    }
    return 0;
}