#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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 int inf = 1e18;
const int mxn = 2e3+50;
const int F = 2;
const int LO = 0, HI = 2e9;
const int mod = 998244353;
int n,m,x;
vector<array<int,2>> adj[mxn];
int dist1[mxn][F*mxn], distn[mxn][F*mxn];
priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> dij;
vector<array<int,2>> line; // first relevant, m, b
int ev(array<int,2> l, int x) {
return l[0]*x+l[1];
}
int first_lower(array<int,2> l1, array<int,2> l2) {
auto [m1,b1] = l1;
auto [m2,b2] = l2;
int x = (b1-b2)/(m2-m1);
while (ev(l1,x) > ev(l2,x)) {x++;}
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});
}
dij.push({0,0,0});
while (sz(dij)) {
auto [d,v,l] = dij.top(); dij.pop();
if (dist1[v][l] <= d) {
continue;
}
dist1[v][l] = d;
if (l==F*n+10) continue;
for (auto [u,dt] : adj[v]) {
dij.push({dt+d,u,l+1});
}
}
dij.push({0,n-1,0});
while (sz(dij)) {
auto [d,v,l] = dij.top(); dij.pop();
if (distn[v][l] <= d) {continue;}
distn[v][l] = d;
if (l==F*n+10) continue;
for (auto [u,dt] : adj[v]) {
dij.push({dt+d,u,l+1});
}
}
line.clear();
for (int i=0; i<n; i++) {
for (auto [j,d] : adj[i]) {
int 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));
vector<array<int,4>> revl;
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});
}
}
int 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(x,f);
if (lo%2) lo++;
if (hi%2) hi--;
if (lo>hi) continue;
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
int 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});
}
}
//get sum of odd evaluations
//low - F*n
//high - x
for (auto [m,b,s,f] : revl) {
if (f < F*n) continue;
if (s > x) continue;
int lo = max(F*n,s), hi = min(x,f);
if (lo%2==0) lo++;
if (hi%2==0) hi--;
if (lo>hi) continue;
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;
}
for (int d=0; d<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;
}