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

const int N = 2e3+5, MOD = 998244353, M = 5e3;

typedef long long int lint;

lint mat[N][4*N][2];
lint edges[M][3];

vector<array<lint, 2>> con[N];

void solve(){
	//memset(mat, 0, sizeof(mat));
	lint n, m, X;
	scanf("%lld %lld %lld", &n, &m, &X);
	for (int x = 0; x < n; x ++){
		con[x].clear();
	}
	for (int x = 0; x < n; x ++){
		for (int y = 0; y <= 4*n; y ++){
			mat[x][y][0] = mat[x][y][1] = 0;
		}
	}
	for (int x = 0; x < m; x ++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);

		a --, b --;
		con[a].push_back({b, c});
		con[b].push_back({a, c});

		edges[x][0] = a;
		edges[x][1] = b;
		edges[x][2] = c;
	}
	for (int c = 0; c < 2; c ++){
		queue<array<lint, 2>> que;

		if (c == 0) que.push({0, 0});
		else que.push({n-1, 0});

		while (!que.empty()){
			array<lint, 2> cur = que.front();
			que.pop();
			lint i = cur[0], t = cur[1];
			if (t == 4*n){
				continue;
			}
			for (array<lint, 2> e: con[i]){
				int j = e[0];
				if (!mat[j][t+1][c]){
					mat[j][t+1][c] = mat[i][t][c] + e[1];
					que.push({j, t+1});
				}else {
					mat[j][t+1][c] = min(mat[j][t+1][c], mat[i][t][c] + e[1]);
				}
			}
		}
		//for (int x = 0; x < n; x ++){
			//for (int y = 0; y <= 4*n; y ++){
				//printf("%lld ", mat[x][y][c]);
			//}
			//printf("\n");
		//}
		//cout << "------------------" << endl;
	}
	lint sum = 0;
	for (int x = 0; x <= min(4*n, X); x ++){
		sum += mat[n-1][x][0];
		sum %= MOD;
	}

	array<lint, 4> bestE = {(lint)2e18, (lint)2e18, 0, 0};
	array<lint, 4> bestO = {(lint)2e18, (lint)2e18, 0, 0};
	array<lint, 4> bestS = {(lint)2e18, (lint)2e18, 0, 0};
	for (int x = 0; x < m; x ++){
		{
			int a = edges[x][0], b = edges[x][1];
			lint c = edges[x][2];
			lint dist1O = 2e18;
			lint dist1E = 2e18;
			lint dist2O = 2e18;
			lint dist2E = 2e18;
			for (int i = 0; i <= 2*n; i ++){
				if (i & 1){
					if ((a == 0 && i == 0) || mat[a][i][0]) dist1O = min(dist1O, mat[a][i][0] + (2*n-i) * c);
					if ((b == n-1 && i == 0) || mat[b][i][1]) dist2O = min(dist2O, mat[b][i][1] + (2*n-i) * c);
				}else {
					if ((a == 0 && i == 0) || mat[a][i][0]) dist1E = min(dist1E, mat[a][i][0] + (2*n-i) * c);
					if ((b == n-1 && i == 0) || mat[b][i][1]) dist2E = min(dist2E, mat[b][i][1] + (2*n-i) * c);
				}
			}
			if (a == b){
				lint dist1 = min(dist1O, dist1E);
				lint dist2 = min(dist2O, dist2E);
				bestS = min(bestS, (array<lint, 4>){edges[x][2], dist1+dist2, a, b});
			}
			bestE = min(bestE, (array<lint, 4>){edges[x][2], dist1E+dist2E, a, b});
			bestE = min(bestE, (array<lint, 4>){edges[x][2], dist1O+dist2O, a, b});

			bestO = min(bestO, (array<lint, 4>){edges[x][2], dist1E+dist2O-edges[x][2], a, b});
			bestO = min(bestO, (array<lint, 4>){edges[x][2], dist1O+dist2E-edges[x][2], a, b});
		}
		{
			int b = edges[x][0], a = edges[x][1];
			lint c = edges[x][2];
			lint dist1O = 2e18;
			lint dist1E = 2e18;
			lint dist2O = 2e18;
			lint dist2E = 2e18;
			for (int i = 0; i <= 2*n; i ++){
				if (i & 1){
					if ((a == 0 && i == 0) || mat[a][i][0]) dist1O = min(dist1O, mat[a][i][0] + (2*n-i) * c);
					if ((b == n-1 && i == 0) || mat[b][i][1]) dist2O = min(dist2O, mat[b][i][1] + (2*n-i) * c);
				}else {
					if ((a == 0 && i == 0) || mat[a][i][0]) dist1E = min(dist1E, mat[a][i][0] + (2*n-i) * c);
					if ((b == n-1 && i == 0) || mat[b][i][1]) dist2E = min(dist2E, mat[b][i][1] + (2*n-i) * c);
				}
			}
			if (a == b){
				lint dist1 = min(dist1O, dist1E);
				lint dist2 = min(dist2O, dist2E);
				bestS = min(bestS, (array<lint, 4>){edges[x][2], dist1+dist2, a, b});
			}
			bestE = min(bestE, (array<lint, 4>){edges[x][2], dist1E+dist2E, a, b});
			bestE = min(bestE, (array<lint, 4>){edges[x][2], dist1O+dist2O, a, b});

			bestO = min(bestO, (array<lint, 4>){edges[x][2], dist1E+dist2O-edges[x][2], a, b});
			bestO = min(bestO, (array<lint, 4>){edges[x][2], dist1O+dist2E-edges[x][2], a, b});
		}
	}
	//printf("%lld %lld %lld %lld\n", bestO[0], bestO[1], bestO[2], bestO[3]);
	//printf("%lld %lld %lld %lld\n", bestE[0], bestE[1], bestE[2], bestE[3]);
	{
		// insert funny math stuff
		lint s = (X-4*n);
		if (s > 0){
			if (bestE[0] <= bestS[0]){
				if (bestE[1] < 1e18){
					bestE[0] %= MOD;
					bestE[1] %= MOD;
					lint c = s/2;
					c %= MOD;
					sum += c * bestE[1];
					sum %= MOD;
					sum += ((c)*(c+1)/2) % MOD * 2*bestE[0] % MOD;
					sum %= MOD;
				}
				if (bestO[1] < 1e18) {
					bestO[0] %= MOD;
					bestO[1] %= MOD;
					lint c = (s+1)/2;
					c %= MOD;
					sum += c * bestO[1];
					sum %= MOD;
					sum += ((c)*(c+1)/2) % MOD * 2*bestO[0] % MOD;
					sum %= MOD;
				}
			}else {
				bestS[0] %= MOD;
				bestS[1] %= MOD;
				lint c = s;
				c %= MOD;
				sum += c * bestS[1];
				sum %= MOD;
				sum += ((c)*(c+1)/2) % MOD * bestS[0] % MOD;
				sum %= MOD;
			}
		}
	}
	printf("%lld\n", sum);
}

int main(){
	int n;
	scanf("%d", &n);
	for (int x = 0; x < n; x ++){
		solve();
	}
}