/**
 * @author n685
 * @brief
 * @date 2024-09-14 17:58:33
 *
 *
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

template <class T> constexpr T INF = T{};
template <std::floating_point T>
constexpr T INF<T> = std::numeric_limits<T>::infinity();
template <> constexpr int INF<int> = 0x3f3f3f3f; // 1061109567
template <>
constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399

template <class T> constexpr std::pair<T, T> ex_eucl(T a, T b) {
  if (a < b) {
    auto [x, y] = ex_eucl(b, a);
    return {y, x};
  }
  if (b == 0) {
    assert(a == 1);
    return {1, 0};
  }
  auto [x, y] = ex_eucl(b, a % b);
  return {y, x - (a / b) * y};
}

template <class Md, class V = int64_t>
  requires std::signed_integral<std::decay_t<decltype(Md::value)>>
struct Mod {
  using T = std::decay_t<decltype(Md::value)>;
  T val = 0;

  static constexpr T normalize(std::integral auto val) {
    using U = decltype(Md::value + val);
    U uval = static_cast<U>(val);
    U umd = static_cast<U>(Md::value);
    if (uval <= -umd || umd <= uval) {
      uval %= umd;
    }
    if (val < 0) {
      uval += umd;
    }
    return static_cast<T>(uval);
  }
  constexpr Mod() : val(0) {}
  constexpr explicit Mod(std::integral auto _val) : val(normalize(_val)) {}

  static inline const Mod ZERO = Mod(0);
  static inline const Mod ONE = Mod(1);
  static inline const Mod TWO = Mod(2);

  // addition
  constexpr Mod &operator+=(Mod b) {
    val += b.val;
    if (val >= Md::value) {
      val -= Md::value;
    }
    return *this;
  }
  friend constexpr Mod operator+(Mod a, Mod b) { return a += b; }
  constexpr Mod &operator++() { return *this += Mod(1); }
  constexpr Mod operator++(int) {
    Mod res = *this;
    ++(*this);
    return res;
  }

  // subtraction
  constexpr Mod &operator-=(Mod b) {
    val -= b.val;
    if (val < 0) {
      val += Md::value;
    }
    return *this;
  }
  friend constexpr Mod operator-(Mod a, Mod b) { return a -= b; }
  constexpr Mod &operator--() { return *this -= Mod(1); }
  constexpr Mod operator--(int) {
    Mod res = *this;
    --(*this);
    return res;
  }
  // negation
  constexpr Mod operator-() const { return Mod(-val); }

  // multiplication
  constexpr Mod &operator*=(Mod b) {
    val = static_cast<T>(static_cast<V>(val) * b.val % Md::value);
    return *this;
  }
  friend constexpr Mod operator*(Mod a, Mod b) { return a *= b; }
  constexpr Mod binpow(std::integral auto b) const {
    Mod res = Mod(1), a = *this;
    while (b > 0) {
      if (b % 2 == 1) {
        res *= a;
      }
      a *= a;
      b /= 2;
    }
    return res;
  }

  // factorial
  // align with fft, if code fails to compile make this smaller (if using array)
  static constexpr int MXINV = 1 << 22;
  static inline bool init = false;
  static inline std::vector<Mod> ff, iff;
  static void reset_fac() { init = false; }
  static void init_fac() {
    if (init) {
      return;
    }
    ff.resize(MXINV + 1);
    ff[0] = Mod(1);
    for (int i = 1; i <= MXINV; ++i) {
      ff[i] = ff[i - 1] * Mod(i);
    }
    iff.resize(MXINV + 1);
    iff[MXINV] = ff[MXINV].large_inv();
    for (int i = MXINV - 1; i >= 0; --i) {
      iff[i] = iff[i + 1] * Mod(i + 1);
    }
    init = true;
  }
  static Mod fac(int v) {
    if (!init) {
      init_fac();
    }
    return ff[v];
  }
  static Mod ifac(int v) {
    if (!init) {
      init_fac();
    }
    return iff[v];
  }
  static Mod comb(int n, int k) {
    if (n < 0 || k < 0 || n < k) {
      return Mod(0);
    }
    return fac(n) * ifac(n - k) * ifac(k);
  }
  static Mod perm(int n, int k) {
    if (n < 0 || k < 0 || n < k) {
      return Mod(0);
    }
    return fac(n) * ifac(n - k);
  }

  // inverse
  Mod small_inv() const {
    return ifac(static_cast<int>(val)) * fac(static_cast<int>(val) - 1);
  }
  constexpr Mod large_inv() const {
    return Mod(ex_eucl(static_cast<V>(val), static_cast<V>(Md::value)).first);
    // return binpow(Md::value - 2);
  }
  Mod inv() const {
    if (val <= MXINV) {
      return small_inv();
    }
    return large_inv();
  }

  // sqrt
  std::optional<Mod> sqrt() {
    static std::mt19937 rng(
      std::chrono::steady_clock::now().time_since_epoch().count()
    );
    Mod c = Mod::ZERO;
    while ((c * c - *this).binpow((Md::value - 1) / 2) == Mod::ONE) {
      c = Mod(rng());
    }
    if (c == Mod::ZERO) {
      return std::nullopt;
    }
    std::pair<Mod, Mod> res(Mod::ONE, Mod::ZERO), a(c, Mod::ONE);
    T b = (Md::value + 1) / 2;
    auto mul = [&c, this](
                 const std::pair<Mod, Mod> &u,
                 const std::pair<Mod, Mod> &v
               ) -> std::pair<Mod, Mod> {
      return {
        u.first * v.first + u.second * v.second * (c * c - *this),
        u.second * v.first + u.first * v.second
      };
    };
    while (b > 0) {
      if (b % 2 == 1) {
        res = mul(res, a);
      }
      a = mul(a, a);
      b /= 2;
    }
    return res.first;
    // return std::min(res.first, -res.first);
  }

  // comparison
  constexpr bool operator==(const Mod &b) const = default;
  constexpr std::strong_ordering operator<=>(const Mod &b) const = default;

  // io
  friend std::istream &operator>>(std::istream &in, Mod &a) {
    int64_t v;
    in >> v;
    a = Mod(v);
    return in;
  }
  friend std::ostream &operator<<(std::ostream &out, const Mod &a) {
    out << a.val;
    return out;
  }

  // conversion
  constexpr T value() const { return val; }
};

#if defined(LOCAL) && __cplusplus >= 202302L
template <class Md, class V>
  requires std::formattable<typename Mod<Md, V>::T, char>
struct std::formatter<Mod<Md, V>, char> {
  using T = typename Mod<Md, V>::T;
  std::formatter<T, char> underlying;
  constexpr formatter() {
    if constexpr (requires { underlying.set_debug_format(); }) {
      underlying.set_debug_format();
    }
  }
  template <class ParseContext> constexpr auto parse(ParseContext &ctx) {
    return underlying.parse(ctx);
  }
  template <class FormatContext>
  auto format(const Mod<Md, V> &val, FormatContext &ctx) const {
    return underlying.format(val.value(), ctx);
  }
};
#endif

constexpr int MOD = 998'244'353;
using Mint = Mod<std::integral_constant<std::decay_t<decltype(MOD)>, MOD>>;

struct Node {
  int64_t dist;
  int node, level;
  auto operator<=>(const Node &b) const = default;
};
struct Frac {
  __int128_t a, b; // a / b
  auto operator<=>(const Frac &f) const { return a * f.b <=> b * f.a; }
  __int128_t trunc() const { return a / b; }
};
struct Line {
  int64_t a, b;
  auto operator<=>(const Line &b) const = default;
  int64_t operator()(int64_t x) const { return a * x + b; }
  Frac inter(const Line &rhs) const {
    assert(a != rhs.a);
    return Frac{rhs.b - b, a - rhs.a};
  }
};

void solve() {
  int n, m;
  int64_t x;
  std::cin >> n >> m >> x;

  std::vector<std::vector<std::pair<int64_t, int>>> adj(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    int64_t w;
    std::cin >> a >> b >> w;
    --a;
    --b;
    adj[a].emplace_back(w, b);
    adj[b].emplace_back(w, a);
  }

  const int mx = 4 * n;

  std::vector d0(mx + 2, std::vector(n, INF<int64_t>));
  std::vector dn = d0;
  auto sp = [&](int rt, std::vector<std::vector<int64_t>> &dist) {
    dist[0][rt] = 0;
    for (int i = 1; i <= mx + 1; ++i) {
      for (int j = 0; j < n; ++j) {
        for (auto [w, k] : adj[j]) {
          dist[i][j] = std::min(dist[i][j], dist[i - 1][k] + w);
        }
      }
    }
  };
  sp(0, d0);
  Mint ans{0};
  for (int i = 1; i <= std::min<int64_t>(x, mx - 1); ++i) {
    ans += d0[i][n - 1] == INF<int64_t> ? Mint::ZERO : Mint{d0[i][n - 1]};
  }
  if (x <= mx - 1) {
    std::cout << ans << '\n';
    return;
  }
  sp(n - 1, dn);

  std::vector dv(n, std::array<int64_t, 2>{INF<int64_t>, INF<int64_t>});
  std::vector mi(n, INF<int64_t>);
  for (int j = 0; j <= mx; ++j) {
    for (int i = 0; i < n; ++i) {
      dv[i][0] = std::min(dv[i][0], d0[j][i] + dn[mx - j][i]);
    }
  }
  for (int j = 0; j <= mx + 1; ++j) {
    for (int i = 0; i < n; ++i) {
      dv[i][1] = std::min(dv[i][1], d0[j][i] + dn[(mx + 1) - j][i]);
    }
  }
  for (int i = 0; i < n; ++i) {
    for (auto [w, j] : adj[i]) {
      mi[i] = std::min(mi[i], w);
    }
  }
  std::vector<int> ind(n);
  std::iota(ind.begin(), ind.end(), 0);
  rs::sort(ind, {}, [&](int v) { return mi[v]; });

  std::array<std::deque<Line>, 2> dq;
  dq.fill({Line{0, INF<int64_t>}});
  for (int i : ind) {
    if (mi[i] == INF<int64_t>) {
      continue;
    }
    for (int t : {0, 1}) {
      if (dv[i][t] == INF<int64_t>) {
        continue;
      }
      Line l{2 * mi[i], dv[i][t]};
      if (!dq[t].empty() && l.b >= dq[t][0].b) {
        continue;
      }
      while (!dq[t].empty() && l.a == dq[t][0].a) {
        dq[t].pop_front();
      }
      while (std::ssize(dq[t]) > 1
             && l.inter(dq[t][0]) >= dq[t][0].inter(dq[t][1]))
      {
        dq[t].pop_front();
      }
      dq[t].push_front(l);
    }
  }
  for (int t : {0, 1}) {
    int64_t lst = (x - (mx + t)) / 2;
    int64_t cl = 0;
    for (int i = 0; i < std::ssize(dq[t]) - 1; ++i) {
      int64_t cr = static_cast<int64_t>(
        std::min<__int128_t>(lst, dq[t][i].inter(dq[t][i + 1]).trunc())
      );
      ans += Mint{dq[t][i](cl) + dq[t][i](cr)} * Mint{cr - cl + 1}
        * Mint::TWO.inv();
      if (cr == lst) {
        break;
      }
      cl = cr + 1;
    }
  }
  std::cout << ans << '\n';
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int t;
  std::cin >> t;
  for (int i = 0; i < t; ++i) {
    dbg(i + 1);
    solve();
    bar();
  }
}