#include<bits/stdc++.h>
using namespace std;
const int N=2005,P=998244353;
typedef long long ll;
const ll inf=2e18;
int T,n,m,x,ans;
vector<pair<int,int> >e[N];
ll f[N<<2][N],g[N<<2][N],F0[N],F1[N];
vector<pair<ll,ll> >t0,t1;
ll calc(vector<pair<ll,ll> >&t,ll k,int o){
	k=2*k+o;
	ll res=inf;
	for(auto [x,y]:t)res=min(res,x*k+y);
	return res;
}
void solve(vector<pair<ll,ll> >&t,int o){
	int nw=2*n+1-o,lim=x-o>>1;
	while(nw<=lim){
		ll v=calc(t,nw,o);
		if(nw==lim){
			ans=(ans+v)%P;
			return;
		}
		int l=nw+1,r=lim;
		ll d=calc(t,nw+1,o)-v;
		while(l<r){
			int mid=l+r+1>>1;
			if(calc(t,mid,o)==v+d*(mid-nw))l=mid;
			else r=mid-1;
		}
		int ln=l-nw+1;
		ans=(ans+v%P*ln+d%P*(1ll*ln*(ln-1)/2%P))%P;
		nw=l+1;
	}
}
void solve(){
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=n;++i)e[i].clear();
	t0.clear(),t1.clear(),ans=0;
	for(int i=1,x,y,z;i<=m;++i){
		scanf("%d%d%d",&x,&y,&z);
		e[x].push_back({y,z});
		e[y].push_back({x,z});
	}
	for(int i=1;i<=n;++i){
		F0[i]=F1[i]=inf;
		for(int j=0;j<=4*n+1;++j)f[j][i]=g[j][i]=inf;
	}
	f[0][1]=g[0][n]=0;
	for(int i=0;i<=n*4;++i)
		for(int j=1;j<=n;++j)for(auto [x,y]:e[j]){
			f[i+1][x]=min(f[i+1][x],f[i][j]+y);
			g[i+1][x]=min(g[i+1][x],g[i][j]+y);
		}
	for(int i=1;i<=n;++i){
		for(int j=0;j<=n*4;++j){
			F0[i]=min(F0[i],f[j][i]+g[4*n-j][i]);
			F1[i]=min(F1[i],f[j][i]+g[4*n+1-j][i]);
		}
		F1[i]=min(F1[i],f[n*4+1][i]+g[0][i]);
	}
	for(int i=1;i<=n;++i)for(auto [x,y]:e[i])if(x>i){
		if(F0[i]<inf)t0.push_back({y,F0[i]-4ll*n*y});
		if(F1[i]<inf)t1.push_back({y,F1[i]-(4ll*n+1)*y});
	}
	for(int i=1;i<=x&&i<=n*4;++i)if(f[i][n]<inf)ans=(ans+f[i][n])%P;
	if(x<=n*4)return printf("%d\n",ans),void();
	if(!t0.empty())solve(t0,0);
	if(!t1.empty())solve(t1,1);
	printf("%d\n",ans);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}