#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=2e3+5,M=5e3+5,K=600+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(263082);
int n,m,k,X[M],Y[M],Z[M];ll f[4*N][N],g[4*N][N];
pair<ll,ll> A[M];int H,st[M],sh;
db slope(int x,int y){return (A[y].se-A[x].se)*1.0/(A[y].fi-A[x].fi+eps);}
ll calc(ll x,ll y,pair<ll,ll> A){return A.se%mod*(y-x+1)%mod+(y+x)*(y-x+1)/2%mod*A.fi%mod;}
void Solve(){
	int i,j;scanf("%d%d%d",&n,&m,&k);
	for(i=1;i<=m;i++) scanf("%d%d%d",&X[i],&Y[i],&Z[i]);
	for(i=0;i<=4*n+1;i++) fill(f[i]+1,f[i]+n+1,INF),fill(g[i]+1,g[i]+n+1,INF);
	f[0][1]=0;
	for(i=1;i<=4*n+1;i++) {
		for(j=1;j<=m;j++) f[i][Y[j]]=min(f[i][Y[j]],f[i-1][X[j]]+Z[j]),f[i][X[j]]=min(f[i][X[j]],f[i-1][Y[j]]+Z[j]);
	}
	ll ans=0;
	for(i=1;i<=min(4*n,k);i++) if(f[i][n]<INF) ans+=f[i][n];
	ans%=mod;if(k<=4*n){printf("%lld\n",ans);return;}
	g[0][n]=0;
	for(i=1;i<=4*n+1;i++){
		for(j=1;j<=m;j++) g[i][Y[j]]=min(g[i][Y[j]],g[i-1][X[j]]+Z[j]),g[i][X[j]]=min(g[i][X[j]],g[i-1][Y[j]]+Z[j]);
	}
	H=sh=0;for(i=1;i<=m;i++) {
		ll w=INF;
		for(j=0;j<4*n;j++) w=min(w,min(f[j][X[i]]+g[4*n-j-1][Y[i]],f[j][Y[i]]+g[4*n-j-1][X[i]])+Z[i]);
		if(w<=1e17) A[++H]=make_pair(2ll*Z[i],w);
	}
	sort(A+1,A+H+1);
	for(i=1;i<=H;i++) {
		while(sh>1&&slope(st[sh-1],st[sh])>slope(st[sh],i)) sh--;
		st[++sh]=i;
	}
	while(sh>1&&slope(st[sh-1],st[sh])>0) sh--;
	// for(i=1;i<=H;i++) cerr<<A[i].fi<<' '<<A[i].se<<'\n';
	ll pt=1;
	for(i=sh;i>1;i--) {
		ll up=(A[st[i-1]].se-A[st[i]].se)/(A[st[i]].fi-A[st[i-1]].fi);up=min(up,1ll*(k-4*n)/2);
		if(up>=pt) ans+=calc(pt,up,A[st[i]]),pt=up+1;
	}
	if(sh&&pt<=(k-4*n)/2) ans+=calc(pt,(k-4*n)/2,A[st[1]]);
	H=sh=0;for(i=1;i<=m;i++) {
		ll w=INF;
		for(j=0;j<4*n-1;j++) w=min(w,min(f[j][X[i]]+g[4*n-1-j-1][Y[i]],f[j][Y[i]]+g[4*n-1-j-1][X[i]])+Z[i]);
		if(w<=1e17) A[++H]=make_pair(2ll*Z[i],w);
	}
	sort(A+1,A+H+1);
	for(i=1;i<=H;i++) {
		while(sh>1&&slope(st[sh-1],st[sh])>slope(st[sh],i)) sh--;
		st[++sh]=i;
	}
	while(sh>1&&slope(st[sh-1],st[sh])>0) sh--;
	pt=1;
	for(i=sh;i>1;i--) {
		ll up=(A[st[i-1]].se-A[st[i]].se)/(A[st[i]].fi-A[st[i-1]].fi);up=min(up,1ll*(k-4*n+1)/2);
		if(up>=pt) ans+=calc(pt,up,A[st[i]]),pt=up+1;
	}
	if(sh&&pt<=(k-4*n+1)/2) ans+=calc(pt,(k-4*n+1)/2,A[st[1]]);
	printf("%lld\n",ans%mod);
}
int main(){
	int t=1;
	scanf("%d",&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}