//#pragma GCC optimize("trapv")
#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define i128 __int128_t
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

const int BUF_SZ = 1 << 15;
inline namespace Input {
	char buf[BUF_SZ];int pos;int len;
	char next_char() {
	if (pos == len) {pos = 0;
	len = (int)fread(buf, 1, BUF_SZ, stdin);
	if (!len) { return EOF; }}
	return buf[pos++];}
	int read_int() {
	int x;char ch;int sgn = 1;
	while (!isdigit(ch = next_char())) {
	if (ch == '-') { sgn *= -1; }}
	x = ch - '0';
	while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
	return x * sgn;}
}
inline namespace Output {
	char buf[BUF_SZ];int pos;
	void flush_out() {fwrite(buf, 1, pos, stdout);pos = 0;}
	void write_char(char c) {
	if (pos == BUF_SZ) { flush_out(); }
	buf[pos++] = c;}
	void write_int(int x) {
	static char num_buf[100];
	if (x < 0) {write_char('-');x *= -1;}
	int len = 0;
	for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
	write_char((char)('0' + x));
	while (len) { write_char(num_buf[--len]); }
	write_char('\n');}
	void init_output() { assert(atexit(flush_out) == 0); }
}

const i128 inf = 1e18;

const int mxn = 2e3+50;
const i128 F = 8;
const i128 LO = 0;
const i128 HI = 2e9;
const int mod = 998244353;

int n,m,x;
vector<array<int,2>> adj[mxn];
i128 dist1[mxn][F*mxn], distn[mxn][F*mxn];
vector<array<i128,2>> line; // first relevant, m, b
vector<array<i128,4>> revl;

inline int ev(array<i128,2> l, int x) {
	return l[0]*x+l[1];
}
inline int first_lower(array<i128,2> l1, array<i128,2> l2) {
	auto [m1,b1] = l1;
	auto [m2,b2] = l2;
	i128 x = (b1-b2)/(m2-m1);
	int cnt=0;
	while (ev(l1,x) > ev(l2,x)) {x++; cnt++; assert(cnt<10);}
	return x;
}

void solve() {
	n=read_int(),m=read_int(),x=read_int();
	
	for (int i=0; i<n; i++) {adj[i].clear();}
	for (int i=0; i<n; i++) {for (int j=0; j<F*n+20; j++) {dist1[i][j] = distn[i][j] = inf;}}
	
	for (int i=0; i<m; i++) {
		int u=read_int(),v=read_int(),w=read_int(); u--; v--;
		adj[u].push_back({v,w}); adj[v].push_back({u,w});
	}
	dist1[0][0] = 0;
	for (int i=1; i<F*n+10; i++) {
		for (int v=0; v<n; v++) {
			for (auto [u,d] : adj[v]) {
				dist1[u][i] = min(dist1[u][i], dist1[v][i-1]+d);
			}
		}
	}
	distn[n-1][0] = 0;
	for (int i=1; i<F*n+10; i++) {
		for (int v=0; v<n; v++) {
			for (auto [u,d] : adj[v]) {
				distn[u][i] = min(distn[u][i], distn[v][i-1]+d);
			}
		}
	}
	
	line.clear(); revl.clear();
	for (int i=0; i<n; i++) {
		for (auto [j,d] : adj[i]) {
			i128 md0 = inf;
			for (int li=0; li<=F*n; li++) {
				md0 = min(md0, dist1[j][li]+distn[j][F*n-li]);
			}
			if (md0==inf) continue;
			line.push_back({d,md0-F*n*d});
		}
	}
	sort(all(line)); reverse(all(line));
	assert(sz(line)<1e7);
	for (auto [m,b] : line) {
		while (sz(revl)) {
			auto [m1,b1,fp,lp] = revl.back();
			if (ev({m1,b1},fp) >= ev({m,b},fp) && ev({m1,b1},lp) >= ev({m,b},lp)) {
				revl.pop_back();
				if (sz(revl)) {revl.back()[3] = lp;}
			} else {break;}
		}
		if (!sz(revl)) {revl.push_back({m,b,LO,HI}); continue;
		} else {
			auto [m1,b1,fp,lp] = revl.back();
			if (ev({m1,b1},fp)<=ev({m,b},fp) && ev({m1,b1},lp)<=ev({m,b},lp)) {continue;}
			i128 ff = first_lower({m,b},{m1,b1}); assert(ff>fp);
			revl[sz(revl)-1][3] = ff-1; revl.push_back({m,b,ff,HI});
		}
	}
	
	i128 tsu=0;
	
	for (auto [m,b,s,f] : revl) {
		if (f < F*n) continue;
		if (s > x) continue;
		int lo = max(F*n,s), hi = min((i128)x,f);
		if (lo%2) lo++;
		if (hi%2) hi--;
		if (lo>hi) continue;
		m %= mod;
		int num = (hi-lo)/2+1; int avg = (lo+hi)/2;
		int val = ((num*b)%mod+(num*avg)%mod*m)%mod;
		tsu += val; tsu %= mod;
	}
	
	line.clear(); revl.clear();	
	for (int i=0; i<n; i++) {
		for (auto [j,d] : adj[i]) {
			//dist of F*n+1
			i128 md1 = inf;
			for (int li=0; li<=F*n+1; li++) {
				md1 = min(md1, dist1[j][li]+distn[j][F*n+1-li]);
			}
			if (md1==inf) continue;
			line.push_back({d,md1-(F*n+1)*d});
		}
	}
	sort(all(line)); reverse(all(line));
	for (auto [m,b] : line) {
		while (sz(revl)) {
			auto [m1,b1,fp,lp] = revl.back();
			if (ev({m1,b1},fp) >= ev({m,b},fp) && ev({m1,b1},lp) >= ev({m,b},lp)) {
				revl.pop_back();
				if (sz(revl)) {revl.back()[3] = lp;}
			} else {break;}
		}
		if (!sz(revl)) {revl.push_back({m,b,LO,HI}); continue;
		} else {
			auto [m1,b1,fp,lp] = revl.back();
			if (ev({m1,b1},fp)<=ev({m,b},fp) && ev({m1,b1},lp)<=ev({m,b},lp)) {continue;}
			int ff = first_lower({m,b},{m1,b1}); assert(ff>fp);
			revl[sz(revl)-1][3] = ff-1; revl.push_back({m,b,ff,HI});
		}
	}
	for (auto [m,b,s,f] : revl) {
		if (f < F*n) continue;
		if (s > x) continue;
		int lo = max(F*n,s), hi = min((i128)x,f);
		if (lo%2==0) lo++;
		if (hi%2==0) hi--;
		if (lo>hi) continue;
		m %= mod; 
		int num = (hi-lo)/2+1; int avg = (lo+hi)/2; avg %= mod; num %= mod;
		int val = ((num*b)%mod+(num*avg)%mod*m)%mod;
		tsu += val; tsu %= mod;
	}
	
	for (int d=0; d<min((i128)x+1,F*n); d++) {
		tsu+=(dist1[n-1][d]==inf?0:dist1[n-1][d]); tsu %= mod;
	}
	
	write_int(tsu);
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	init_output();
	
	int t = read_int();
	while (t--) {
		solve();
	}
	
	return 0;
}