#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=2002;
const int mod=998244353;
const ll INF=1ll<<60;
int n,m,K;
vector<pii>G[N];
ll f[N<<2][N],g[N<<2][N],ans;
inline void ck(ll &x,ll y){y<x&&(x=y);}
typedef pair<ll,ll> pll;
inline bool cr(pll A,pll B,pll C){
	return (__int128)(B.fi-A.fi)*(C.se-A.se)>(__int128)(C.fi-A.fi)*(B.se-A.se);
}
inline void ad(pll A,ll L,ll R){
	if(L>R)return;
	ll k=A.fi,b=A.se%mod;
	ans=(ans + (R-L+1)*b + (L+R)*(R-L+1)/2%mod*k)%mod;
}
inline void solve(vector<pll>A,ll K){
	sort(A.begin(),A.end());
	rep(i,1,(int)A.size()-1)if(A[i].fi==A[i-1].fi)swap(A[i],A.back()),A.pop_back(),--i;
	static pll st[N];
	int m=A.size(),tp=0;
	st[tp=1]=A[0];
	rep(i,1,m-1){
		for(;tp>1&&!cr(st[tp-1],st[tp],A[i]);--tp);
		st[++tp]=A[i];
	}
	ll lst=1;
	for(;tp>1;--tp){
		pll A=st[tp],B=st[tp-1];
		if(A.se>=B.se)continue;
		ll k=min(K,(B.se-A.se)/(A.fi-B.fi));
		ad(A,lst,k); lst=k+1;
	}
	ad(A[0],lst,K);
}
inline void solve(){
	n=read(),m=read(),K=read();
	rep(i,1,n)G[i].clear();
	rep(i,1,m){
		int u=read(),v=read(),w=read();
		G[u].pb(P(v,w)),G[v].pb(P(u,w));
	}
	int T=4*n+1;
	rep(i,0,T)rep(j,1,n)f[i][j]=g[i][j]=INF;
	f[0][1]=g[0][n]=0;
	rep(i,1,T)rep(j,1,n)for(pii A:G[j]){
		ck(f[i][A.fi],f[i-1][j]+A.se);
		ck(g[i][A.fi],g[i-1][j]+A.se);
	}
	ans=0;
	rep(i,1,min(T,K))if(f[i][n]<INF)ans+=f[i][n],ans%=mod;
	if(K<=T){printf("%lld\n",ans);return;}
	vector<pll>ve0,ve1;
	rep(i,1,n){
		ll a=INF,b=INF,c=INF;
		for(pii A:G[i])c=min(c,(ll)A.se);
		rep(j,0,T-1)a=min(a,f[j][i]+g[T-1-j][i]);
		rep(j,0,T)b=min(b,f[j][i]+g[T-j][i]);
		if(a<INF)ve0.pb(P(2*c,a));
		if(b<INF)ve1.pb(P(2*c,b));
	}
	if(ve0.size())solve(ve0,(K-T+1)/2);
	if(ve1.size())solve(ve1,(K-T)/2);
	printf("%lld\n",ans);
}
int main() {
    //freopen("data.in", "r", stdin);
    //freopen("myans.out","w",stdout);
	int T=read(); while(T--)solve();
    return 0;
}