#include <cstdio>
#include <algorithm>
using namespace std;
int read(){
	char c=getchar();int x=0;
	while(c<48||c>57) c=getchar();
	do x=x*10+(c^48),c=getchar();
	while(c>=48&&c<=57);
	return x;
}
const int L=8003,N=2003,M=5003;
const int P=998244353;
typedef long long ll;
typedef __int128 lll;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,k,rk,lim;
ll Fs[L][N],Ft[L][N];
ll Fe[N],Fo[N];
inline void chmn(ll &x,ll v){if(x>v) x=v;}
int eu[M],ev[M],ew[M];
struct Line{
	ll a,b; // a * x + b
	friend bool operator<(const Line x,const Line y){
		if(x.a^y.a) return x.a>y.a;
		return x.b<y.b;
	}
}w[N];
int stk[N],tp;
inline bool check(int x,int y,int z){
	return (lll)(w[z].b-w[y].b)*(w[x].a-w[z].a)<=(lll)(w[z].b-w[x].b)*(w[y].a-w[z].a);
}
int S(int l,int r){return ((ll)(l+r)*(r-l+1)>>1)%P;}
int calc(int lim){
	sort(w+1,w+rk+1);
	int las=0,res=0;
	tp=0;
	for(int i=1;i<=rk;++i){
		if(tp&&w[stk[tp]].a==w[i].a) continue;
		while(tp>1&&check(stk[tp-1],stk[tp],i)) --tp;
		stk[++tp]=i;
	}
	for(int i=1;i<=tp;++i){
		ll sp=i==tp?lim:(w[stk[i+1]].b-w[stk[i]].b)/(w[stk[i]].a-w[stk[i+1]].a);
		if(sp>lim) sp=lim;
		res=(res+w[stk[i]].a%P*S(las+1,sp)+w[stk[i]].b%P*(sp-las))%P;
		las=sp;
		if(las==lim) break;
	}
	return res;
}
void solve(){
	n=read();m=read();k=read();lim=n<<2;
	for(int i=1;i<=m;++i) eu[i]=read(),ev[i]=read(),ew[i]=read();
	for(int x=0;x<=lim;++x)
		for(int i=1;i<=n;++i) Fs[x][i]=Ft[x][i]=INF;
	Fs[0][1]=Ft[0][n]=0;
	for(int x=0;x<lim;++x)
		for(int i=1;i<=m;++i){
			chmn(Fs[x+1][eu[i]],Fs[x][ev[i]]+ew[i]);
			chmn(Fs[x+1][ev[i]],Fs[x][eu[i]]+ew[i]);
			chmn(Ft[x+1][eu[i]],Ft[x][ev[i]]+ew[i]);
			chmn(Ft[x+1][ev[i]],Ft[x][eu[i]]+ew[i]);
		}
	int res=0;
	for(int i=1;i<=lim&&i<=k;++i) if(Fs[i][n]!=INF) res=(res+Fs[i][n])%P;
	if(Fs[lim][n]==INF&&Fs[lim-1][n]==INF){puts("0");return;}
	if(k<=lim){printf("%d\n",res);return;}
	for(int x=1;x<=n;++x) Fe[x]=Fo[x]=INF;
	for(int i=0;i<=lim;++i)
		for(int x=1;x<=n;++x) chmn(Fe[x],Fs[i][x]+Ft[lim-i][x]);
	for(int i=0;i<lim;++i)
		for(int x=1;x<=n;++x) chmn(Fo[x],Fs[i][x]+Ft[lim-i-1][x]);
	rk=0;
	for(int i=1;i<=m;++i){
		if(Fe[eu[i]]!=INF) w[++rk]=(Line){2*ew[i],Fe[eu[i]]};
		if(Fe[ev[i]]!=INF) w[++rk]=(Line){2*ew[i],Fe[ev[i]]};
	}
	res+=calc((k-lim)>>1);
	if(res>=P) res-=P;
	rk=0;
	for(int i=1;i<=m;++i){
		if(Fo[eu[i]]!=INF) w[++rk]=(Line){2*ew[i],Fo[eu[i]]};
		if(Fo[ev[i]]!=INF) w[++rk]=(Line){2*ew[i],Fo[ev[i]]};
	}
	res+=calc((k-lim+1)>>1);
	if(res>=P) res-=P;
	printf("%d\n",res);
}
int main(){
	int tc=read();
	while(tc--) solve();
	return 0;
}