#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;

const int maxn = 2050;
const int mod  = 998244353;
const int inv2 = (mod+1)>>1;
const int inf  = 1e15;
inline void down(int &a,const int &b){ if(a>b)a=b; }

vector< pair<int,int> >E[maxn];
int n,m,X;

int d1[10005][maxn],dn[10005][maxn];
int solve()
{
	ll U=min((ll)X,10000ll);
	for(int i=1;i<=n;i++)
		d1[0][i]=dn[0][i]=inf;
	d1[0][1]=0,dn[0][n]=0;
	
	int ret=0;
	
	for(int t=1;t<=U;t++)
	{
		for(int i=1;i<=n;i++) d1[t][i]=inf;
		for(int i=1;i<=n;i++)
		{
			for(auto [j,c]:E[i]) 
				down(d1[t][j],d1[t-1][i]+c);
		}
		
		for(int i=1;i<=n;i++) dn[t][i]=inf;
		for(int i=1;i<=n;i++)
		{
			for(auto [j,c]:E[i]) 
				down(dn[t][j],dn[t-1][i]+c);
		}
		
		if(d1[t][n]!=inf) ret+=d1[t][n]%mod;
		
	//	if(U-t<=10) cerr<<t<<" : "<<d1[n]<<endl;
	}
	return ret%mod;
}
struct line
{
	int x,y,k,t;
	friend inline bool operator <(const line &k1,const line &k2)
	{
		return k1.k>k2.k;
	}
};
vector<line>V[2];
//map< line,int >S;
line S[maxn<<4]; int sl,sr;

int calct(line k1,line k2)
{
	assert(k1.k>=k2.k);
	// k1.k>=k2.k
	int l=0,r=X/2+1;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if( k1.y+k1.k*(mid-k1.x) >= k2.y+k2.k*(mid-k2.x) ) r=mid-1;
		else l=mid+1;
	}
	return r+1;
}

int cal(const int ty)
{
	int l= (ty==0?10002/2:10001/2),r= (X%2==ty)?X/2:(X-1)/2;
	if(l>r) return 0;
	
	for(auto &x:V[ty])
	{
		x.k<<=1;
		x.x/=2;
	}
	
	sort(V[ty].begin(),V[ty].end());
	sl=1,sr=0;
	for(auto x:V[ty])
	{
		if(sl<=sr) S[sr].t= calct(S[sr],x);
		S[++sr]=x;
		while(sl+2<=sr && S[sr-2].t>=S[sr-1].t)
		{
			sr--;
			S[sr]=S[sr+1];
			S[sr-1].t=calct(S[sr-1],S[sr]);
		}
	}
	
	int ret=0;
	while(l<=r)
	{
		while(sl<sr && S[sl].t<=l)
		{
			sl++;
		}
		
		int nex=min(r, sl+1<=sr ? S[sl].t-1 : inf );
		//upd l
		
		//assert(!S.empty());
		if(sl<=sr)
		{
			line now= S[sl];
			ret+= (nex-l+1)%mod*inv2%mod*( (now.y+(l-now.x)*now.k%mod + now.y+(nex-now.x)*now.k%mod)%mod )%mod;
		}
		l=nex+1;
	}
	
	return ret%mod;
}
int calc()
{
	if(10000>=X) return 0;
	
	V[0].clear(); V[1].clear();
	for(int i=1;i<=n;i++) for(auto [j,c]:E[i])
	{
		int temp=inf;
		for(int t=0;t<=10000;t++) temp=min(temp, d1[t][i]+dn[10000-t][i]);
		V[0].emplace_back( 10000,temp,c,0 );
		
		temp=inf;
		for(int t=0;t<=9999;t++) temp=min(temp, d1[t][i]+dn[9999-t][i]);
		V[1].emplace_back( 9999,temp,c,0 );
		
	}
	int c0= cal(0), c1=cal(1);
	return c0+c1;
}

signed main()
{
	ios_base::sync_with_stdio(false); ////////////////////////////////////////
	cin.tie(0);
	
	ll Tcase; cin>>Tcase;
	while(Tcase--)
	{
		cin>>n>>m>>X;
		for(int i=1;i<=n;i++)
		{
			vector<pair<int,int> >_;
			E[i].swap(_);
		}
		for(int i=1;i<=m;i++)
		{
			ll x,y,w; cin>>x>>y>>w;
			E[x].emplace_back(y,w);
			E[y].emplace_back(x,w);
		}
		int ret= solve();
		
		ret+= calc();
		
		cout<<(long long)(ret%mod)<<'\n';
	}
	
	return 0;
}