#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
const int P=998244353;
long long p=1ll*P*P;
inline int mul(const int &a,const int &b){return 1ll*a*b%P;}
inline int sub(int a,const int &b){a-=b;return (a<0)?a+P:a;}
inline int add(int a,const int &b){a+=b;return(a>=P)?a-P:a;}
int qsm(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=mul(ans,a);
        a=mul(a,a);
        b>>=1;
    }
    return ans;
}
typedef std::vector<int> poly;
poly interpolate(poly x,poly f){
    poly tem,ans(x.size());
    tem.push_back(1);
    for(int i=0;i<x.size();++i){
        tem.push_back(0);
        for(int j=tem.size()-1;~j;--j)
            tem[j]=sub(j?tem[j-1]:0,mul(tem[j],x[i]));
    }
    for(int i=0;i<x.size();++i){
        for(int j=0;j<x.size();++j)
            if(i!=j)f[i]=mul(f[i],qsm(sub(x[i],x[j]),P-2));
        poly ttem=tem;
        int inv=qsm(x[i],P-2);
        for(int j=0;j<ttem.size();++j)ttem[j]=mul(sub(j?ttem[j-1]:0,ttem[j]),inv);
//    for(int i=0;i<ttem.size();++i)printf("%d ",ttem[i]);putchar('\n');
        for(int j=0;j<ans.size();++j)ans[j]=add(ans[j],mul(f[i],ttem[j]));
    }
    return ans;
}
const int N=101;
struct matrix{
    int siz;
    int num[N][N];
    matrix(int S=0){
        siz=S;
        memset(num,0,sizeof num);
    }
    matrix operator*(matrix a){
        matrix c(siz);
        for(int i=0;i<siz;++i)
            for(int j=0;j<siz;++j){
                long long x=0;
                for(int k=0;k<siz;++k)
                    if((x+=1ll*num[i][k]*a.num[k][j])>=p)x-=p;
                c.num[i][j]=x%P;
            }
        return c;
    }
    int det(){
        matrix a=*this;
        int ans=1;
        for(int i=0;i<siz;++i){
            for(int j=i;j<siz;++j)
                if(a.num[j][i]){
                    std::swap(a.num[j],a.num[i]);
                    if(j!=i)ans=sub(0,ans);
                }
            ans=mul(ans,a.num[i][i]);
            int inv=qsm(a.num[i][i],P-2);
            for(int j=i+1;j<siz;++j)
                if(a.num[j][i]){
                    int Mul=mul(inv,a.num[j][i]);
                    for(int k=0;k<siz;++k)
                        a.num[j][k]=sub(a.num[j][k],mul(a.num[i][k],Mul));
                }
        }
        return ans;
    }
    matrix adjugate_brute(){
        matrix ans(siz);
        for(int i=0;i<siz;++i)
            for(int j=0;j<siz;++j){
                matrix tem(siz-1);
                for(int k=0;k<siz;++k)
                    for(int l=0;l<siz;++l)
                        if(k!=i&&l!=j)
                            tem.num[k-(k>i)][l-(l>j)]=num[k][l];
                ans.num[i][j]=(((i+j)&1)?sub:add)(0,tem.det());
            }
        return ans;
    }
    matrix inv(int &ans){
        matrix c(siz),a=*this;
        for(int i=0;i<siz;++i)
            for(int j=0;j<siz;++j)
                c.num[i][j]=(i==j);
        ans=1;
        for(int i=0;i<siz;++i){
            for(int j=i;j<siz;++j)
                if(a.num[j][i]){
                    std::swap(a.num[j],a.num[i]);
                    std::swap(c.num[j],c.num[i]);
                    break;
                }
            ans=mul(ans,a.num[i][i]);
            if(!a.num[i][i]){
                return c;
            }
            int inv=qsm(a.num[i][i],P-2);
            for(int j=0;j<siz;++j)c.num[i][j]=mul(c.num[i][j],inv);
            for(int j=i;j<siz;++j)a.num[i][j]=mul(a.num[i][j],inv);
            for(int j=i+1;j<siz;++j)
                if(a.num[j][i]){
                    for(int k=0;k<siz;++k)
                        c.num[j][k]=sub(c.num[j][k],mul(c.num[i][k],a.num[j][i]));
                    for(int k=siz-1;k>=i;--k)
                        a.num[j][k]=sub(a.num[j][k],mul(a.num[i][k],a.num[j][i]));
                }
        }
        for(int i=siz-1;~i;--i)
            for(int j=i-1;~j;--j)
                if(a.num[j][i]){
                    for(int k=0;k<siz;++k)
                        c.num[j][k]=sub(c.num[j][k],mul(c.num[i][k],a.num[j][i]));
                    a.num[j][i]=0;
                }
        return c;
    }
    void T(){
        for(int i=0;i<siz;++i)
            for(int j=i+1;j<siz;++j)
                std::swap(num[i][j],num[j][i]);
    }
    void gaussian(){
        for(int i=0;i<siz;++i){
            for(int j=i;j<siz;++j)
                if(num[j][i]){
                    std::swap(num[j],num[i]);
                    break;
                }
            if(num[i][i]){
                int inv=qsm(num[i][i],P-2);
                for(int k=0;k<siz;++k)
                    num[i][k]=mul(num[i][k],inv);
                for(int j=i+1;j<siz;++j)
                    if(num[j][i]){
                        for(int k=siz-1;k>=i;--k)
                            num[j][k]=sub(num[j][k],mul(num[i][k],num[j][i]));
                    }
            }
//            out();
        }
        for(int i=siz-1;~i;--i)
            if(num[i][i])
                for(int j=i-1;~j;--j)
                    if(num[j][i]){
                        for(int k=siz-1;k>=i;--k)
                            num[j][k]=sub(num[j][k],mul(num[i][k],num[j][i]));
                    }
    }
    matrix adjugate(){
        int det;
        matrix tem=inv(det),ans(siz);
        memset(ans.num,0,sizeof ans.num);
        if(det){
            for(int i=0;i<siz;++i)
                for(int j=0;j<siz;++j)
                    ans.num[i][j]=mul(tem.num[j][i],det);
            return ans;
        }
        matrix a=*this,b=*this;
        b.T();
        a.gaussian(),b.gaussian();
        int cnt=0;
        for(int i=0;i<siz;++i)cnt+=(a.num[i][i]==0);
        if(cnt>1)return ans;
        b.T();
//        a.out();
//        b.out();
        int p1,p2;
        for(int i=0;i<siz;++i)if(!a.num[i][i])p1=i;
        for(int i=0;i<siz;++i)if(!b.num[i][i])p2=i;
        matrix Tem(siz-1);
        for(int i=0;i<siz;++i)
            for(int j=0;j<siz;++j)
                if(i!=p1&&j!=p2)
                    Tem.num[i-(i>p1)][j-(j>p2)]=num[i][j];
        ans.num[p1][p2]=Tem.det();
        for(int i=p2-1;~i;--i){
            for(int j=i+1;j<=p2;++j)
                ans.num[p1][i]=sub(ans.num[p1][i],mul(ans.num[p1][j],b.num[j][i]));
            ans.num[p1][i]=mul(ans.num[p1][i],qsm(b.num[i][i],P-2));
        }
//        ans.out();
        for(int i=p1-1;~i;--i)
            for(int j=p2;~j;--j){
                for(int k=i+1;k<=p1;++k)
                    ans.num[i][j]=sub(ans.num[i][j],mul(a.num[i][k],ans.num[k][j]));
                ans.num[i][j]=mul(ans.num[i][j],qsm(a.num[i][i],P-2));
            }
        ans.T();
        return ans;
    }
    int heisen_det(){
//        out();
        matrix a=*this;
        int ans=1;
        for(int i=0;i<siz;++i){
            for(int j=i;j<=i+1&&j<siz;++j)
                if(a.num[j][i]){
                    std::swap(a.num[j],a.num[i]);
                    if(j!=i)ans=sub(0,ans);
                    break;
                }
            ans=mul(ans,a.num[i][i]);
            int inv=qsm(a.num[i][i],P-2);
            for(int j=i+1;j==i+1&&j<siz;++j)
                if(a.num[j][i]){
//                    printf("%d %d\n",i,j);
                    int Mul=mul(inv,a.num[j][i]);
                    for(int k=0;k<siz;++k)
                        a.num[j][k]=sub(a.num[j][k],mul(a.num[i][k],Mul));
                }
        }
        return ans;
    }
    poly Char(){
        matrix a=*this;
        for(int i=0;i<siz-1;++i){
            for(int j=i+1;j<siz;++j)
                if(a.num[j][i]){
                    for(int k=0;k<siz;++k)std::swap(a.num[i+1][k],a.num[j][k]);
                    for(int k=0;k<siz;++k)std::swap(a.num[k][i+1],a.num[k][j]);
                    break;
                }
            for(int j=i+2;j<siz;++j)
                if(a.num[j][i]){
                    int Mul=sub(0,mul(a.num[j][i],qsm(a.num[i+1][i],P-2)));
                    for(int k=0;k<siz;++k)a.num[j][k]=add(a.num[j][k],mul(a.num[i+1][k],Mul));
                    for(int k=0;k<siz;++k)a.num[k][i+1]=sub(a.num[k][i+1],mul(a.num[k][j],Mul));
                }
//        a.out();
        }
        for(int i=0;i<siz;++i)
            for(int j=0;j<siz;++j)
                a.num[i][j]=sub(0,a.num[i][j]);
        poly x,f;
        for(int i=1;i<=siz+1;++i){
            for(int j=0;j<siz;++j)a.num[j][j]=add(a.num[j][j],1);
            x.push_back(i);
            f.push_back(a.heisen_det());
        }
//        for(int i=0;i<x.size();++i)printf("%d ",x[i]);putchar('\n');
//        for(int i=0;i<f.size();++i)printf("%d ",f[i]);putchar('\n');
        return interpolate(x,f);
    }
    void out(){
        puts("---");
        for(int i=0;i<siz;++i,putchar('\n'))
            for(int j=0;j<siz;++j)
                printf("%d ",num[i][j]);
    }
}ans;
matrix qsm(matrix a,int n){
    ans.siz=a.siz;
    for(int i=0;i<a.siz;++i)
        for(int j=0;j<a.siz;++j)
            ans.num[i][j]=(i==j);
    while(n){
        if(n&1)ans=ans*a;
        a=a*a;
        n>>=1;
    }
    return ans;
}
int n,m,k,t,d[101];
int main(){
    scanf("%d",&t);
    for(int fd=1;fd<=t;++fd){
        scanf("%d%d%d",&n,&m,&k);
        matrix a(n),b(n);
        for(int i=0;i<n;++i)d[i]=0;
        for(int i=1,u,v,w;i<=m;++i){
            scanf("%d%d%d",&u,&v,&w);
            --u,--v;
            ++d[u],++d[v];
            if(!w)a.num[u][v]=a.num[v][u]=1;
            else b.num[u][v]=b.num[v][u]=1;
        }
        for(int i=0;i<n;++i)d[i]=qsm(d[i],P-2);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j){
                a.num[i][j]=mul(a.num[i][j],d[i]);
                b.num[i][j]=mul(b.num[i][j],d[i]);
            }
        matrix c(n);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                c.num[i][j]=add(a.num[i][j],b.num[i][j]);
        int x=qsm(c,k).num[0][n-1];
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                c.num[i][j]=sub(a.num[i][j],b.num[i][j]);
        int y=qsm(c,k).num[0][n-1];
        printf("%d\n",mul(sub(x,y),(P+1)>>1));
    }
}