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

#define int long long
#define ar(x) array<int,x>
#define pb push_back
#define U(x) ((int)x.size())
const int N=2e3+100,INF=1e18,MOD=998244353;
inline void mod(int &x){ if(x>=MOD) x-=MOD; if(x<0) x+=MOD; }
inline int qm(int x,int y=MOD-2){ int res=1; for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD; return res; }
inline int chkmin(int &x,int y){ return y<x?x=y,1:0; }
#define gc getchar()
#define rd read()
inline int read(){
	int x=0,f=0; char c=gc;
	for(;c<'0'||c>'9';c=gc) f|=(c=='-');
	for(;c>='0'&&c<='9';c=gc) x=(x<<1)+(x<<3)+(c^48);
	return f?-x:x;
}

int n,m,K,ans=0,inv2,f[N*4][N],g[N*4][N],F0[N],F1[N];
vector<ar(2)> G[N],odd,even;

inline int calc(ar(2) lin,int x){ return (lin[0]*x+lin[1]); }
ar(2) find(const vector<ar(2)> &vc,int x){
	int mn=INF; ar(2) res;
	for(auto [k,b]:vc) if(chkmin(mn,calc({k,b},x))) res={k,b};
	return res;
}

void solve(){
	n=rd,m=rd,K=rd,ans=0; for(int i=1,x,y,z;i<=m;++i) x=rd,y=rd,z=rd,G[x].pb({y,z}),G[y].pb({x,z});
	
	for(int i=0;i<=4*n+1;++i) for(int j=1;j<=n;++j) f[i][j]=g[i][j]=INF; f[0][1]=g[0][n]=0;
	for(int i=1;i<=4*n+1;++i) for(int u=1;u<=n;++u) for(auto [v,w]:G[u]) chkmin(f[i][v],f[i-1][u]+w),chkmin(g[i][v],g[i-1][u]+w);
	for(int i=1,mn;i<=n;++i){
		F0[i]=F1[i]=mn=INF;
		for(int j=0;j<=4*n+1;++j){
			if(j<=4*n) chkmin(F0[i],f[j][i]+g[4*n-j][i]);
			chkmin(F1[i],f[j][i]+g[4*n+1-j][i]);
		}
		for(auto [v,w]:G[i]){
			if(F0[i]!=INF) even.pb({w,F0[i]-4*n*w});
			if(F1[i]!=INF) odd.pb({w,F1[i]-(4*n+1)*w});
		}
	}
	
	for(int i=1;i<=4*n&&i<=K;++i) if(f[i][n]!=INF) mod(ans+=f[i][n]%MOD);
/*
	for(auto [k,b]:even){
		cout<<k<<" "<<b<<"\n";
	}
	puts("");
	for(auto [k,b]:odd){
		cout<<k<<" "<<b<<"\n";
	}
*/

	//even
	if(U(even)){
		for(int i=2*n+1,l,r;i*2<=K;i=l+1){
			l=i,r=K/2; auto [k,b]=find(even,i*2);
			while(l<r){
				int mid=l+r>>1;
				if(find(even,mid*2)[0]==k) l=mid+1;
				else r=mid-1;
			}
			mod(ans+=(calc({k,b},i*2)%MOD+calc({k,b},l*2)%MOD)*(l-i+1)%MOD*inv2%MOD);
		}
	}
	//odd
	if(U(odd)){
		for(int i=2*n,l,r;i*2+1<=K;i=l+1){
			l=i,r=(K-1)/2; auto [k,b]=find(odd,i*2+1);
			while(l<r){
				int mid=l+r>>1;
				if(find(odd,mid*2+1)[0]==k) l=mid+1;
				else r=mid-1;
			}
			mod(ans+=(calc({k,b},i*2+1)%MOD+calc({k,b},l*2+1)%MOD)*(l-i+1)%MOD*inv2%MOD);
		}	
	}
	
	printf("%lld\n", ans);
	
	for(int i=1;i<=n;++i) G[i]={}; odd={},even={};
}

signed main(){
	
	inv2=qm(2);
	
	int T=rd;
	while(T--) solve();
	
	return 0;
}

/*
4 6 1000000000
1 2 244
1 2 325
1 4 927
3 3 248
2 4 834
3 4 285
*/