#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 5000
#define mod 998244353
using namespace std;
const long long inf=(long long)(1e18);
const int INF=(int)(1e9)+1;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
struct reads
{
	int num,data;
};
struct points
{
	int x;
	long long y;
	bool operator < (const points &t)const
	{
		return x!=t.x?x<t.x:y<t.y;	
	}
};
points tong[N+1],dque[N+1];
int T,n,m,t,top,ans,length,minn[N+1];
long long dp[N+1][N+1],dp2[N+1][N+1],sminn[2],sminn2[2];
vector<reads>E[N+1];
void add(int x,int y,int z)
{
	minn[x]=min(minn[x],z),minn[y]=min(minn[y],z),E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
	return;
}
bool check(points a,points b,points c)
{
	return (__int128)(b.y-a.y)*(c.x-a.x)>=(__int128)(c.y-a.y)*(b.x-a.x);
}
long long get(long long a,int b)
{
	if (!b) return a>=0?inf:-inf;
	else if (a>=0) return a/b+1;
	else return -(-a-1)/b;
}
long long get2(long long a,int b)
{
	if (!b) return a>=0?inf:-inf;
	else if (a>=0) return a/b;
	else return -(-a+b-1)/b;
}
void calc(int x)
{
	long long l,r;
	sort(tong+1,tong+length+1),top=0;
	for (int i=1;i<=length;++i)
	{
		while (top>=2&&check(dque[top-1],dque[top],tong[i])) top--;
		dque[++top]=tong[i];
	}
	for (int i=1;i<=top;++i)
	{
		l=0,r=x;
		if (i+1<=top) l=max(l,get(dque[i].y-dque[i+1].y,dque[i+1].x-dque[i].x));
		if (i-1>=1) r=min(r,get2(dque[i-1].y-dque[i].y,dque[i].x-dque[i-1].x));
		if (l<=r)
		{
			Adder(ans,(r-l+1)*(dque[i].y%mod)%mod);
			Adder(ans,(((r*(r+1)>>1)-((l*(l-1))>>1))%mod)*dque[i].x%mod);
		}
	}
	return;
}
int main()
{
	int x,y,z,d;
	T=read();
	while (T--)
	{
		n=read(),m=read(),t=read(),ans=0;
		for (int i=1;i<=n;++i) E[i].clear(),minn[i]=INF;
		for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),add(x,y,z);
		for (int i=0;i<=(n<<1)+2;++i)
			for (int j=1;j<=n;++j)
				dp[i][j]=dp2[i][j]=inf;
		dp[0][1]=dp2[0][n]=0;
		for (int i=1;i<=(n<<1)+2;++i)
			for (int j=1;j<=n;++j)
				for (int k=0;k<E[j].size();++k)
					dp[i][j]=min(dp[i][j],dp[i-1][E[j][k].num]+E[j][k].data),dp2[i][j]=min(dp2[i][j],dp2[i-1][E[j][k].num]+E[j][k].data);
		for (int i=0;i<=min(t,(n<<1)+2);++i)
			if (dp[i][n]!=inf)
				Adder(ans,dp[i][n]%mod);
		if (t>=(n<<1)+3&&dp[(n<<1)+1][n]!=inf)
		{
			d=(t-(n<<1)-3)>>1,length=0;
			for (int i=1;i<=n;++i)
				if (minn[i]!=INF)
				{
					for (int op=0;op<=1;++op) sminn[op]=sminn2[op]=inf;
					for (int j=0;j<=n+1;++j) sminn[j&1]=min(sminn[j&1],dp[j][i]-1ll*minn[i]*j),sminn2[j&1]=min(sminn2[j&1],dp2[j][i]-1ll*minn[i]*j);
					if (min(sminn[0]+sminn2[1],sminn[1]+sminn2[0])+1ll*minn[i]*((n<<1)+3)<inf) tong[++length]=(points){minn[i]<<1,min(sminn[0]+sminn2[1],sminn[1]+sminn2[0])+1ll*minn[i]*((n<<1)+3)};
				}
			calc(d);
		}
		if (t>=(n<<1)+4&&dp[(n<<1)+2][n]!=inf)
		{
			d=(t-(n<<1)-4)>>1,length=0;
			for (int i=1;i<=n;++i)
				if (minn[i]!=INF)
				{
					for (int op=0;op<=1;++op) sminn[op]=sminn2[op]=inf;
					for (int j=0;j<=n+1;++j) sminn[j&1]=min(sminn[j&1],dp[j][i]-1ll*minn[i]*j),sminn2[j&1]=min(sminn2[j&1],dp2[j][i]-1ll*minn[i]*j);
					if (min(sminn[0]+sminn2[0],sminn[1]+sminn2[1])+1ll*minn[i]*((n<<1)+4)<inf) tong[++length]=(points){minn[i]<<1,min(sminn[0]+sminn2[0],sminn[1]+sminn2[1])+1ll*minn[i]*((n<<1)+4)};
				}
			calc(d);
		}
		printf("%d\n",ans);
	}
	return 0;
}