#include<bits/stdc++.h>
#define db double
#define reg register
#define LL long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ull unsigned long long
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(int i=head[a];i;i=e[i].nxt)


using namespace std;
bool Handsome;
inline int rd(){
    reg int x=0;reg char o=getchar();reg bool O=0;
    for(;o<48 || 57<o;o=getchar())if(o=='-')O=1;
    for(;48<=o && o<=57;o=getchar())x=(x<<1)+(x<<3)+(o^48);
    return O?-x:x;
}
inline void Mi(int &x,int y){if(x>y && (x=y));}
inline void Mx(int &x,int y){if(x<y && (x=y));}
const int M=105,P=998244353;
int n,m,k,d[M];
void Add(int &x,int y){
    x+=y;
    if(x>=P)x-=P;
    if(x<0)x+=P;
}
int FAST(int x,int y){
    int res=1;
    for(;y;y>>=1){
        if(y&1)res=1ll*res*x%P;
        x=1ll*x*x%P;
    }
    return res;
}
struct Mtx{
    int a[M][M][2];
    Mtx (){memset(a,0,sizeof(a));}
    void clr(){memset(a,0,sizeof(a));}
    Mtx operator * (const Mtx &x)const{
        Mtx y;
        rep(i,1,n)rep(j,1,n)rep(k,1,n){
            Add(y.a[i][k][0],1ll*a[i][j][0]*x.a[j][k][0]%P);
            Add(y.a[i][k][1],1ll*a[i][j][0]*x.a[j][k][1]%P);
            Add(y.a[i][k][1],1ll*a[i][j][1]*x.a[j][k][0]%P);
            Add(y.a[i][k][0],1ll*a[i][j][1]*x.a[j][k][1]%P);
        }
        return y;
    }
}A,ANS;

void Clear(){
    memset(d,0,sizeof(d));
    A.clr();ANS.clr();
}
void solve(){
    n=rd();m=rd();k=rd();
    rep(i,1,m){
        int x=rd(),y=rd(),z=rd();
        A.a[x][y][z]=A.a[y][x][z]=1;
        ++d[x];++d[y];
    }
    rep(i,1,n){
        int z=FAST(d[i],P-2);
        rep(j,1,n){
            A.a[i][j][0]=1ll*A.a[i][j][0]*z%P;
            A.a[i][j][1]=1ll*A.a[i][j][1]*z%P;
        }
    }
    ANS.a[1][1][0]=1;
    for(;k;k>>=1){
        if(k&1)ANS=ANS*A;
        A=A*A;
    }
    printf("%d\n",ANS.a[1][n][1]);
}
bool Most;
int main(){
//    printf("%.2lfMB\n",(&Most-&Handsome)/1024.0/1024.0);
    int t=rd();
    while(t--)Clear(),solve();
    return 0;
}