#include<bits/stdc++.h>
using namespace std;
using namespace std;
const long double eps=1e-10l;
const long double inf=1e14l;
const long double pi=acosl(-1.0l);
const long double s2=sqrtl(2);
struct vec//点或者向量
{
	long double x,y;
	vec operator +(const vec &a)const{return (vec){x+a.x,y+a.y};}
	vec operator -(const vec &a)const{return (vec){x-a.x,y-a.y};}
	long double operator *(const vec &a)const{return x*a.x+y*a.y;}//向量点乘
	vec operator *(const long double &a)const{return (vec){x*a,y*a};}//向量数乘(向量在左)
	vec operator /(const long double &a)const{return (vec){x/a,y/a};}//向量数除(向量在左)
	bool operator !=(const vec &a)const{return fabsl(a.x-x)>eps||fabsl(a.y-y)>eps;}
	bool operator ==(const vec &a)const{return fabsl(a.x-x)<=eps&&fabsl(a.y-y)<=eps;}
	bool operator <(const vec &a)const{return fabsl(x-a.x)>eps?(x<a.x):(y<a.y);}
	bool operator >(const vec &a)const{return fabsl(x-a.x)>eps?(x>a.x):(y>a.y);}
	bool operator <=(const vec &a)const{return fabsl(x-a.x)>eps?(x<a.x+eps):(y<a.y+eps);}
	bool operator >=(const vec &a)const{return fabsl(x-a.x)>eps?(x>a.x-eps):(y>a.y-eps);}
	long double operator ^(const vec &a)const{return x*a.y-y*a.x;}//向量叉乘
	friend ostream &operator <<(ostream &out,vec &a){return out<<a.x<<" "<<a.y;}
	friend istream &operator >>(istream &in,vec &a){return in>>a.x>>a.y;}
	vec rev(long double r){long double now=r+arg(),d=hypotl(x,y);return (vec){d*cos(now),d*sin(now)};}//向量逆时针旋转
	long double arg(){return atan2l(y,x);}//向量辐角
};
struct line//直线，存储直线上一点 a 和方向向量 d；或者线段，两端点分别为 a 和 a+d
{
	vec a,d;
	long double arg(){return d.arg();}
	long double slop(){if(fabsl(d.x)<eps)return d.y/fabsl(d.y)*inf;return d.y/d.x;}//求斜率
	long double gety(long double x){if(fabsl(d.x)<eps)return inf;return a.y+(x-a.x)/d.x*d.y;}//由x求y
	long double getx(long double y){if(fabsl(d.y)<eps)return inf;return a.x+(y-a.y)/d.y*d.x;}//由x求y
};
long double dis(vec a,vec b){return hypotl(a.x-b.x,a.y-b.y);}//两点间距
long double dis(vec a){return hypotl(a.x,a.y);}//向量模长
long double dis(vec a,line b){return fabsl((a-b.a)^b.d)/dis(b.d);}//点到直线之间的距离
bool check_left(vec a,vec b){return (a^b)>eps;}//检查 b 向量是否在 a 向量的左侧
bool check_right(vec a,vec b){return (a^b)<-eps;}//检查 b 向量是否在 a 向量的左侧
vec sec(line a,line b)//两直线交点，平行或重合返回(inf,inf)
{
	if(fabsl(a.d^b.d)<=eps)
		return {inf,inf};
	vec u=a.a-b.a;
	long double t=(b.d^u)/(a.d^b.d);
	return a.a+a.d*t;
}
vec pro(vec a,line b){return sec(b,(line){a,b.d.rev(pi/2)});}//求点在直线上的投影
bool check_in(line a,vec b){vec t1=a.a,t2=a.a+a.d;if(fabs((t1-b)^(t2-b))>eps)return 0;if(t1>t2)swap(t1,t2);return b>=t1&&b<=t2;}//判断点是否在线段内(含端点)
bool check(line t1,line t2){if(fabs(t1.d^t2.d)<=eps)return 0;return check_in(t1,sec(t1,t2));}//判断线段是否相交(重合视为不相交)
struct polygon//多边形，逆时针存点，请在末尾添加第一个点！
{
	vector<vec> nd;
	void init(){nd.push_back(nd[0]);}
	void push_back(vec a){nd.push_back(a);}
	long double C(){long double sum=0;for(int i=0;i<=(int)nd.size()-2;i++)sum+=dis(nd[i],nd[i+1]);return sum;}//求多边形的周长
	long double S(){long double sum=0;for(int i=1;i<=(int)nd.size()-3;i++)sum+=((nd[i]-nd[0])^(nd[i+1]-nd[0]));return fabsl(sum)/2;}//求多边形的面积
	int chk(vec b)//判断点和多边形的位置关系，多边形内返回-1，多边形上返回0，多边形外返回1
	{
		for(int i=0;i<(int)nd.size()-1;i++)
			if(check_in({nd[i],nd[i+1]-nd[i]},b))
				return 0;
		line a={b,{1,s2}};
		int cnt=0;
		for(int i=0;i<(int)nd.size()-1;i++)
		{
			line p={nd[i],nd[i+1]-nd[i]};
			vec now=sec(p,a);
			if(now>b&&check_in(p,now))
				cnt++;
		}
		if(cnt&1)
			return -1;
		return 1;
	}
};
struct cir//圆
{
	vec a;
	long double r;
	long double C(){return 2*pi*r;}//求圆的周长
	long double S(){return pi*r*r;}//求圆的面积
	int chk(vec b){long double d=dis(a,b);if(d<r-eps)return -1;else if(d<r+eps)return 0;return 1;}//判断点和圆的位置关系，圆内返回-1，圆上返回0，圆外返回1
};
bool in(cir a,vec b){return dis(a.a,b)<=a.r+eps;}//判断点是否在圆内部
pair<vec,vec> sec(cir a,cir b)//求两圆的交点，相切算作两个交点，无交点返回(inf,inf)
{
	long double d=dis(a.a,b.a);
	if(d>a.r+b.r+eps||d<fabs(a.r-b.r)-eps)
		return make_pair((vec){inf,inf},(vec){inf,inf});
	long double p=acos((a.r*a.r+d*d-b.r*b.r)/2.0/d/a.r);
	vec ri=b.a-a.a;ri=ri*(a.r/d);
	return make_pair(a.a+ri.rev(p),a.a+ri.rev(-p));
}
pair<vec,vec> sec(cir a,line b)//求圆与直线的交点，相切算作两个交点，无交点返回(inf,inf)
{
	long double d=dis(a.a,b);
	if(d>a.r+eps)
		return make_pair((vec){inf,inf},(vec){inf,inf});
	long double q=sqrtl(a.r*a.r-d*d);
	line c=(line){a.a,b.d.rev(pi/2)};
	vec t=sec(b,c);
	b.d=b.d/dis(b.d)*q;
	return make_pair(t-b.d,t+b.d);
}

const int maxn=2200;
const int maxm=5100;
const int lim=10000;
const int mod=998244353;
int T,n,m,x;
int u[maxm],v[maxm],w[maxm];
long long f[maxn][lim+5],g[maxn][lim+5];
vector<pair<int,int> > G[maxn];

line e[maxm],L[maxm];
vec N[maxm];
int top=0,id[maxm],hd=1,tl=0;
long double ag[maxm];
bool cmp1(int a,int b)
{
	if(fabsl(ag[a]-ag[b])>=eps)
		return ag[a]<ag[b];
	if((e[b].d^(e[a].a-e[b].a))>eps)
		return 1;
	return 0;
}
bool cmp2(int a,int b){return fabsl(ag[a]-ag[b])<eps;}
void solve()
{
	hd=1,tl=0;
	for(int i=1;i<=top;i++)
		id[i]=i,ag[i]=e[i].arg();
	sort(id+1,id+top+1,cmp1);
	top=unique(id+1,id+top+1,cmp2)-id-1;
	for(int i=1;i<=top;i++)
	{
		line now=e[id[i]];
		while(hd<=tl&&(now.d^(N[tl]-now.a))<-eps)
			tl--;
		while(hd<=tl&&(now.d^(N[hd]-now.a))<-eps)
			hd++;
		if(i!=1)
			tl++,N[tl]=sec(L[tl],now);
		L[tl+1]=now;
	}
	while(hd<=tl&&(L[hd].d^(N[tl]-L[hd].a))<-eps)
		tl--;
	if(tl-hd>=1)
		tl++,N[tl]=sec(L[tl],L[hd]),N[hd-1]=N[tl];
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&m,&x);
		for(int i=1;i<=n;i++)
		{
			G[i].clear();
			for(int j=0;j<=lim;j++)
				f[i][j]=g[i][j]=1e18;
		}
		for(int i=1;i<=m;i++)
			scanf("%d%d%d",&u[i],&v[i],&w[i]),G[u[i]].emplace_back(v[i],w[i]),G[v[i]].emplace_back(u[i],w[i]);
		if(n==1)
		{
			puts("0");
			continue;
		}
		f[1][0]=0,g[n][0]=0;
		for(int i=0;i<lim;i++)
			for(int x=1;x<=n;x++)
				for(auto [t,val]:G[x])
					f[t][i+1]=min(f[t][i+1],f[x][i]+val),g[t][i+1]=min(g[t][i+1],g[x][i]+val);
		int cnt=0;
		for(int i=1;i<=lim&&i<=x;i++)
			cnt=(cnt+(f[n][i]==1e18?0:f[n][i]))%mod;
		if(x>lim)
		{
			if(f[n][lim]!=1e18)
			{
				top=0;
				for(int i=1;i<=m;i++)
				{
					long long mn0=1e18;
					for(int j=0;j<lim;j++)
						mn0=min({mn0,w[i]+f[u[i]][j]+g[v[i]][lim-1-j],w[i]+f[v[i]][j]+g[u[i]][lim-1-j]});
					if(mn0<1e18)
						e[++top]={{lim,(long double)mn0},{-1,-(long double)w[i]}};
				}
				e[++top]={{(long double)x,0},{0,1}};
				e[++top]={{(long double)(lim+1),0},{0,-1}};
				e[++top]={{0,0},{1,0}};
				solve();
				for(int i=hd;i<=tl-2;i++)
				{
					int l=int(N[i].x+eps)+1,r=int(N[i-1].x+eps);
					if(l&1)
						l++;
					if(r&1)
						r--;
					long long fi=(long long)(L[i].gety((long double)l)+eps),la=(long long)(L[i].gety((long double)r)+eps);
					cnt=(cnt+1ll*(la+fi)%mod*((r-l)/2+1)%mod*(mod+1)/2)%mod;
				}
			}
			if(f[n][lim-1]!=1e18)
			{
				top=0;
				for(int i=1;i<=m;i++)
				{
					long long mn1=1e18;
					for(int j=0;j<lim-1;j++)
						mn1=min({mn1,w[i]+f[u[i]][j]+g[v[i]][lim-2-j],w[i]+f[v[i]][j]+g[u[i]][lim-2-j]});
					if(mn1<1e18)
						e[++top]={{lim-1,(long double)mn1},{-1,-(long double)w[i]}};
				}
				e[++top]={{(long double)x,0},{0,1}};
				e[++top]={{(long double)(lim),0},{0,-1}};
				e[++top]={{0,0},{1,0}};
				solve();
				for(int i=hd;i<tl;i++)
				{
					int l=int(N[i].x+eps)+1,r=int(N[i-1].x+eps);
					if(!(l&1))
						l++;
					if(!(r&1))
						r--;
					long long fi=(long long)(L[i].gety((long double)l)+eps),la=(long long)(L[i].gety((long double)r)+eps);
					cnt=(cnt+1ll*(la+fi)%mod*((r-l)/2+1)%mod*(mod+1)/2)%mod;
				}
			}
		}
		printf("%d\n",cnt);
	}
	
	return 0;
}