/**
 * @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;
};
template <class T> struct Line {
  T a, b;
  auto operator<=>(const Line &b) const = default;
  T operator()(T x) const { return a * x + b; }
};
template <class T, class Comp = std::less<>> struct LiChao {
  static constexpr Comp comp{};
  struct Node {
    Line<T> line{0, INF<T>};
    std::array<int, 2> ch{-1, -1};
    bool is_leaf() const { return ch[0] == -1 && ch[1] == -1; }
  };
  T lb{}, ub{};
  std::vector<Node> data{Node()};
  LiChao() = default;
  explicit LiChao(T r) : ub{r} {}
  LiChao(T l, T r) : lb{l}, ub{r} {}
  void alloc(int &ch, Line<T> line) {
    ch = static_cast<int>(data.size());
    data.push_back(Node{line});
  }
  void upd(Line<T> line, int ind, T l, T r) {
    if (l == r) {
      if (comp(line(l), data[ind].line(l))) {
        data[ind].line = line;
      }
      return;
    }
    T mid = std::midpoint(l, r);
    bool llt = comp(line(l), data[ind].line(l));
    bool mlt = comp(line(mid), data[ind].line(mid));
    if (mlt) {
      std::swap(line, data[ind].line);
    }
    if (llt != mlt) {
      if (data[ind].ch[0] != -1) {
        upd(line, data[ind].ch[0], l, mid);
      } else {
        alloc(data[ind].ch[0], line);
      }
    } else if (data[ind].ch[1] != -1) {
      upd(line, data[ind].ch[1], mid + 1, r);
    } else {
      alloc(data[ind].ch[1], line);
    }
  }
  void upd(Line<T> line) { upd(line, 0, lb, ub); }
  void upd(T a, T b) { upd(Line{a, b}); }
  Mint sum(T x, int node, T l, T r, std::vector<Line<T>> &lines) {
    if (l > x) {
      return Mint::ZERO;
    }
    if (node != -1) {
      lines.push_back(data[node].line);
    }
    if (node == -1 || data[node].is_leaf()) {
      Line<T> mi{0, INF<T>};
      for (Line<T> &line : lines) {
        if (comp(line(l), mi(l))) {
          mi = line;
        }
      }
      if (node != -1) {
        lines.pop_back();
      }
      return Mint{mi(l) + mi(std::min(r, x))} * Mint{std::min(r, x) - l + 1}
      * Mint::TWO.inv();
    }
    int64_t mid = (l + r) / 2;
    Mint ans = sum(x, data[node].ch[0], l, mid, lines)
      + sum(x, data[node].ch[1], mid + 1, r, lines);
    lines.pop_back();
    return ans;
  }
  Mint sum(T x) {
    std::vector<Line<T>> lines;
    Mint ans = sum(x, 0, lb, ub, lines);
    assert(lines.empty());
    return ans;
  }
};

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 = 20000;

  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::array<LiChao<int64_t>, 2> dq;
  dq.fill(LiChao<int64_t>(0, x));
  for (int i = 0; i < n; ++i) {
    if (mi[i] == INF<int64_t>) {
      continue;
    }
    for (int t : {0, 1}) {
      if (dv[i][t] == INF<int64_t>) {
        continue;
      }
      dq[t].upd(2 * mi[i], dv[i][t]);
    }
  }
  for (int t : {0, 1}) {
    if (dq[t].data.size() == 1) {
      continue;
    }
    int64_t lst = (x - (mx + t)) / 2;
    ans += dq[t].sum(lst);
  }
  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();
  }
}