#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll mod = 998244353;
// #include <brawlstars>
// FOR PAIN OR FOR GLORYYY ELLL PRIMOOOOOO

const ll N = 2001, M = 5001;
ll dis[2][4 * N][N], dist[2][N], cnt, ans;
pii cht[2 * M];
bool comp(const pii &a, const pii &b) {
	if(a.f == b.f) return a.s < b.s;
	return a.f > b.f;
}
long double slope(pii a, pii b) {
	return -1 * (a.s - b.s) / (a.f - b.f);
}
void bk(ll n) {
	sort(cht, cht + cnt, comp);
	vector<ll> stk;
	for(ll i = 0; i < cnt; i++) {
		if(stk.size() && cht[stk.back()].f == cht[i].f) continue;
		ll j = stk.size() - 2;
		while(j >= 0 && slope(cht[stk[j]], cht[stk.back()]) <= slope(cht[stk.back()], cht[i])) stk.pop_back(), j--;
		stk.push_back(i);
	}
	ll prv = 0, nxt;
	pii cur;
	for(ll i = 0; i < (ll)stk.size(); i++) {
		nxt = n;
		if(i != (ll)stk.size() - 1) nxt = min(n, (ll)slope(cht[stk[i]], cht[stk[i + 1]]));
		if(nxt <= 0) continue;
		cur = cht[stk[i]], cur.f %= mod, cur.s %= mod;
		ans = (ans + (prv + nxt + 1) * (nxt - prv) / 2 % mod * cur.f + (nxt - prv) * cur.s) % mod;
		prv = nxt;
		if(prv == n) break;
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll t;
	cin >> t;
	while(t--) {
		ll n, m, x;
		cin >> n >> m >> x;
		ans = 0;
		pair<pii, ll> edges[m];
		for(ll i = 0; i < m; i++) cin >> edges[i].f.f >> edges[i].f.s >> edges[i].s;
		for(ll i = 0; i <= 4 * n; i++) {
			for(ll j = 0; j <= n; j++) dis[0][i][j] = dis[1][i][j] = 1e18;
		}
		dis[0][0][1] = dis[1][0][n] = 0;
		for(ll i = 1; i <= 4 * n; i++) {
			for(auto j : edges) {
				dis[0][i][j.f.s] = min(dis[0][i][j.f.s], dis[0][i - 1][j.f.f] + j.s);
				dis[0][i][j.f.f] = min(dis[0][i][j.f.f], dis[0][i - 1][j.f.s] + j.s);
				dis[1][i][j.f.s] = min(dis[1][i][j.f.s], dis[1][i - 1][j.f.f] + j.s);
				dis[1][i][j.f.f] = min(dis[1][i][j.f.f], dis[1][i - 1][j.f.s] + j.s);
			}
		}
		if(dis[0][4 * n][n] == 1e18 && dis[0][4 * n - 1][n] == 1e18) {
			cout << "0\n";
			continue;
		}
		for(ll i = 1; i <= min(4 * n, x); i++) {
			if(dis[0][i][n] != 1e18) ans = (ans + dis[0][i][n]) % mod;
		}
		if(x <= 4 * n) {
			cout << ans << "\n";
			continue;
		}
		for(ll i = 1; i <= n; i++) dist[0][i] = dist[1][i] = 1e18;
		for(ll i = 0; i <= 4 * n; i++) {
			for(ll j = 1; j <= n; j++) dist[0][i] = min(dist[0][i], dis[0][i][j] + dis[1][4 * n - i][j]);
			if(i == 4 * n) break;
			for(ll j = 1; j <= n; j++) dist[1][i] = min(dist[1][i], dis[0][i][j] + dis[1][4 * n - i - 1][j]);
		}
		cnt = 0;
		for(ll i = 0; i < m; i++) {
			if(dist[0][edges[i].f.f] != 1e18) cht[cnt] = {2 * edges[i].s, dist[0][edges[i].f.f]}, cnt++;
			if(dist[0][edges[i].f.s] != 1e18) cht[cnt] = {2 * edges[i].s, dist[0][edges[i].f.s]}, cnt++;
		}
		bk((x - 4 * n) / 2);
		cnt = 0;
		for(ll i = 0; i < m; i++) {
			if(dist[1][edges[i].f.f] != 1e18) cht[cnt] = {2 * edges[i].s, dist[1][edges[i].f.f]}, cnt++;
			if(dist[1][edges[i].f.s] != 1e18) cht[cnt] = {2 * edges[i].s, dist[1][edges[i].f.s]}, cnt++;
		}
		bk((x - 4 * n + 1) / 2);
		cout << ans << "\n";
	}
}