#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=998244353;
const ll N=2010,M=5010;
const ll inf=1e18;

struct edge {
	ll x,y,c,next;
} a[2*M];
ll len,last[N];

void ins(ll x,ll y,ll c) {
	a[++len].x=x;
	a[len].y=y;
	a[len].c=c;
	a[len].next=last[x];
	last[x]=len;
}

ll st[N][4*N],ed[N][4*N];
ll Ans,n,m,lim;
ll Odd1[N],Odd2[N],Even1[N],Even2[N];

struct line {
	ll k,b;
	ll op;
};
map<ll, line> g;
ll tot,sta[8*M],cnt,sum,List[8*M];

bool cmp(ll n1,ll n2) {
	if(g[n1].k==g[n2].k) return (g[n1].b>=g[n2].b);
	return (g[n1].k>=g[n2].k);
}

ll doit(ll x1,ll x2) {
	if(g[x2].b<g[x1].b) return 0;
	return (g[x2].b-g[x1].b+g[x1].k-g[x2].k-1)/(g[x1].k-g[x2].k);
}

ll calc(ll L,ll R,ll x) {
	return (((R-L)/2+1)* (g[x].b%mod) + ((R+L)/2)*((R-L)/2+1)%mod*g[x].k)%mod;
}

void solve(ll op) {
	tot=0;
	sum=0;
	for(ll i=1; i<=cnt; i++)
		if(g[i].op==op) List[++sum]=i;
	sort(List+1,List+sum+1,cmp);
	for(ll i=1; i<=sum; i++) {
		if(i<=sum&&g[List[i]].k==g[List[i+1]].k) continue;
		while(tot>=1&&doit(sta[tot-1],sta[tot])>doit(sta[tot],List[i])) tot--;
		sta[++tot]=List[i];
	}

	// for(ll i=1;i<=tot;i++) prllf("%lld %lld\n",g[sta[i]].k,g[sta[i]].b);

	for(ll i=1; i<=tot; i++) {
		ll L=4*n+2,R=lim;
		if(i>=1) L=max(L,doit(sta[i-1],sta[i]));
		if(i<tot) R=min(R,doit(sta[i],sta[i+1])-1);
		if(L%2!=op) L++;
		if(R%2!=op) R--;
		if(L<=R) Ans=(Ans+calc(L,R,sta[i]))%mod;//,prllf("%lld %lld %lld %lld\n",L,R,g[sta[i]].k,g[sta[i]].b);
	}
}

int main()
{

	ll T;
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d%d",&n,&m,&lim);
		len=0;
		for(ll i=1; i<=n; i++) last[i]=0;
		for(ll i=1; i<=m; i++) {
			ll x,y,c;
			scanf("%d%d%d",&x,&y,&c);
			ins(x,y,c);
			ins(y,x,c);
		}

		for(ll i=0; i<=4*n+1; i++)
			for(ll j=1; j<=n; j++)
				st[j][i]=ed[j][i]=inf;
		st[1][0]=ed[n][0]=0;
		// prllf("!!! %d\n",n);
		for(ll i=0; i<4*n+1; i++)
			for(ll j=1; j<=n; j++)
				for(ll k=last[j]; k; k=a[k].next) {
					ll y=a[k].y;
					st[y][i+1]=min(st[y][i+1],st[j][i]+a[k].c);
					ed[y][i+1]=min(ed[y][i+1],ed[j][i]+a[k].c);
				}

		Ans=0;
		for(ll i=1; i<=4*n+1&&i<=lim; i++)
			if(st[n][i]!=inf) Ans=(Ans+st[n][i])%mod;

		/*for(ll i=1;i<=n;i++){
		    ll id1=-1,id2=-1,id3=-1,id4=-1;
		    for(ll j=4*n+1;j>=0;j--){
		        if(st[i][j]!=inf){
		            if(j&1) id1=j;
		            else id2=j;
		        }

		        if(ed[i][j]!=inf){
		            if(j&1) id3=j;
		            else id4=j;
		        }
		    }
		    Odd1[i]=id1; Odd2[i]=id3;
		    Even1[i]=id2; Even2[i]=id4;
		}*/

		// prllf("%d %d %d %d\n",Odd1[1],Even1[1],Odd2[2],Even2[2]);
		/*for(ll i=1;i<=n;i++){
		    ll id1=-1,id2=-1,id3=-1,id4=-1;
		    for(ll j=4*n+1;j>=0;j--){
		        if(st[i][j]!=inf){
		            if(j&1) id1=j;
		            else id2=j;
		        }

		        if(ed[i][j]!=inf){
		            if(j&1) id3=j;
		            else id4=j;
		        }
		    }
		    Odd1[i]=id1; Odd2[i]=id3;
		    Even1[i]=id2; Even2[i]=id4;
		}*/

		// prllf("%d %d %d %d\n",Odd1[1],Even1[1],Odd2[2],Even2[2]);

		cnt=0;
		for(ll i=1; i<=len; i++) {
			//id1 + id3 -> dis[id1] + dis[id3]
			ll id1=-1,id2=-1,id3=-1,id4=-1;
			for(ll j=2*n; j>=0; j--) {
				if(st[a[i].x][j]!=inf) {
					if(j&1) {
						if(id1==-1||st[a[i].x][j]-(ll)j*a[i].c<=st[a[i].x][id1]-(ll)id1*a[i].c)
							id1=j;
					}
					else {
						if(id2==-1||st[a[i].x][j]-(ll)j*a[i].c<=st[a[i].x][id2]-(ll)id2*a[i].c)
							id2=j;
					}
				}

				if(ed[a[i].y][j]!=inf) {
					if(j&1) {
						if(id3==-1||ed[a[i].y][j]-(ll)j*a[i].c<=ed[a[i].y][id3]-(ll)id3*a[i].c)
							id3=j;
					}
					else {
						if(id4==-1||ed[a[i].y][j]-(ll)j*a[i].c<=ed[a[i].y][id4]-(ll)id4*a[i].c)
							id4=j;
					}
				}
			}
			Odd1[a[i].x]=id1;
			Odd2[a[i].y]=id3;
			Even1[a[i].x]=id2;
			Even2[a[i].y]=id4;

			if(Odd1[a[i].x]!=-1&&Odd2[a[i].y]!=-1) g[++cnt].k=a[i].c, g[cnt].b=st[a[i].x][Odd1[a[i].x]]+ed[a[i].y][Odd2[a[i].y]]-(ll)a[i].c*(Odd1[a[i].x]+Odd2[a[i].y]), g[cnt].op=1;

			if(Even1[a[i].x]!=-1&&Even2[a[i].y]!=-1) g[++cnt].k=a[i].c, g[cnt].b=st[a[i].x][Even1[a[i].x]]+ed[a[i].y][Even2[a[i].y]]-(ll)a[i].c*(Even1[a[i].x]+Even2[a[i].y]), g[cnt].op=1;

			if(Odd1[a[i].x]!=-1&&Even2[a[i].y]!=-1) g[++cnt].k=a[i].c, g[cnt].b=st[a[i].x][Odd1[a[i].x]]+ed[a[i].y][Even2[a[i].y]]-(ll)a[i].c*(Odd1[a[i].x]+Even2[a[i].y]), g[cnt].op=0;

			if(Even1[a[i].x]!=-1&&Odd2[a[i].y]!=-1) g[++cnt].k=a[i].c, g[cnt].b=st[a[i].x][Even1[a[i].x]]+ed[a[i].y][Odd2[a[i].y]]-(ll)a[i].c*(Even1[a[i].x]+Odd2[a[i].y]), g[cnt].op=0;
		}

		solve(0);
		solve(1);

		printf("%d\n",Ans);
	}

	return 0;
}