/**
 * @author n685
 * @brief
 * @date 2024-09-20 21:20:01
 *
 *
 */
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif
#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 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(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(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(__cpp_lib_format) && __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>>;

using i128 = __int128_t;

template <class T>
concept integral = std::integral<T> || std::is_same_v<i128, T>;

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 <>
constexpr i128 INF<i128> = (static_cast<i128>(INF<int64_t>) << 64)
  | INF<int64_t>; // 84069761239290679208598432424319205183

struct Edge {
  int u, v;
  i128 w;
};

i128 abs_i128(i128 a) { return a < 0 ? -a : a; }
i128 k = 0;
Mint kmint;
// (ak + b) / c
struct Frac {
  i128 a = 0, b = 0;
  int c = 1;
  Frac &operator+=(i128 rhs) {
    b += c * rhs;
    return *this;
  }
  bool is_inf() const { return c == 0; }
  auto operator<=>(const Frac &rhs) const {
    using ord = std::strong_ordering;
    if (is_inf()) {
      if (rhs.is_inf()) {
        return ord::equal;
      }
      return ord::greater;
    }
    if (rhs.is_inf()) {
      return ord::less;
    }
    i128 al = a * rhs.c, bl = b * rhs.c;
    i128 ar = rhs.a * c, br = rhs.b * c;
    if (al == ar) {
      return bl <=> br;
    }
    if (al < ar && bl <= br) {
      return ord::less;
    }
    if (al > ar && bl >= br) {
      return ord::greater;
    }
    i128 ii = (abs_i128(bl - br) + abs_i128(al - ar) - 1) / abs_i128(al - ar);
    if (al < ar) {
      if (ii >= k) {
        return ord::greater;
      }
      return ord::less;
    }
    if (ii < k) {
      return ord::greater;
    }
    return ord::less;
  }
  Mint to_mint() const { return (Mint{a} * kmint + Mint{b}) * Mint{c}.inv(); }
};
const Frac FINF{0, 1, 0};
const Frac operator+(Frac lhs, i128 rhs) { return lhs += rhs; }

clock_t tot = 0;
clock_t tot2 = 0;
clock_t tot3 = 0;
const std::string infk = []() {
  i128 val = INF<i128>;
  std::string ans;
  while (val > 0) {
    ans += static_cast<char>('0' + val % 10);
    val /= 10;
  }
  rs::reverse(ans);
  return ans;
}();

void solve() {
  auto start = clock();
  int n, m;
  std::string sk;
  std::cin >> n >> m >> sk;
  const int thres = n * n;
  if (sk.size() > infk.size() || (sk.size() == infk.size() && sk > infk)) {
    k = INF<i128>;
  } else {
    for (char c : sk) {
      k = 10 * k + (c - '0');
    }
  }
  std::vector<int> mk(n + 1);
  for (char c : sk) {
    kmint = kmint * Mint{10} + Mint{c - '0'};
    for (int i = 1; i <= n; ++i) {
      mk[i] = (mk[i] * 10 + (c - '0')) % i;
    }
  }

  std::vector<Edge> edges(m);
  for (auto &[u, v, w] : edges) {
    int64_t ww;
    std::cin >> u >> v >> ww;
    --u;
    --v;
    w = ww;
  }

  std::vector dist(n + 1, std::vector(n, std::vector<i128>(n, INF<i128>)));
  std::vector d0(thres + 1, std::vector<i128>(n, INF<i128>));
  d0[0][0] = 0;
  for (int i = 0; i < n; ++i) {
    dist[0][i][i] = 0;
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < n; ++j) {
      for (auto &[u, v, w] : edges) {
        dist[i][j][v] = std::min(dist[i][j][v], dist[i - 1][j][u] + w);
      }
    }
    d0[i] = dist[i][0];
  }
  for (int i = n + 1; i <= thres; ++i) {
    for (auto &[u, v, w] : edges) {
      d0[i][v] = std::min(d0[i][v], d0[i - 1][u] + w);
    }
  }
  tot += clock() - start;
  start = clock();
  if (k <= 3 * thres) {
    int kk = static_cast<int>(k);
    d0.resize(3 * thres + 1, std::vector<i128>(n, INF<i128>));
    for (int i = thres + 1; i <= 3 * thres; ++i) {
      for (auto &[u, v, w] : edges) {
        d0[i][v] = std::min(d0[i][v], d0[i - 1][u] + w);
      }
    }
    for (int i = 0; i < n; ++i) {
      if (d0[kk][i] == INF<i128>) {
        std::cout << "-1 ";
      } else {
        std::cout << static_cast<int>(d0[kk][i] % MOD) << ' ';
      }
    }
    std::cout << '\n';
    return;
  }

  std::vector dp(thres + 1, std::vector<Frac>(n, FINF));
  for (int i = 0; i < n; ++i) {
    i128 mi = INF<i128> / n;
    int sz = 1;
    for (int j = 1; j <= n; ++j) {
      if (dist[j][i][i] != INF<i128> && dist[j][i][i] * sz < mi * j) {
        mi = dist[j][i][i];
        sz = j;
      }
    }
    if (mi == INF<i128> / n) {
      continue;
    }
    for (int j = thres - n; j <= thres; ++j) {
      if (d0[j][i] == INF<i128>) {
        continue;
      }
      int rem = (mk[sz] - j - thres + sz - 1) % sz;
      if (rem < 0) {
        rem += sz;
      }
      dp[thres - sz + 1 + rem][i] = std::min(
        dp[thres - sz + 1 + rem][i],
        Frac{mi, d0[j][i] * sz + mi * (-j - thres + sz - 1 - rem), sz}
      );
    }
  }
  tot2 += clock() - start;
  start = clock();
  for (int i = thres - 1; i >= 0; --i) {
    for (const auto &[u, v, w] : edges) {
      if (!dp[i + 1][u].is_inf()) {
        if (dp[i][v].is_inf()) {
          dp[i][v] = dp[i + 1][u] + w;
        } else {
          dp[i][v] = std::min(dp[i][v], dp[i + 1][u] + w);
        }
      }
    }
  }
  tot3 += clock() - start;
  for (int i = 0; i < n; ++i) {
    if (dp[0][i].is_inf()) {
      std::cout << "-1 ";
    } else {
      std::cout << Mint(dp[0][i].to_mint()) << ' ';
    }
  }
  std::cout << '\n';
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif
  // std::freopen("input.txt", "r", stdin);

  int s, t;
  std::cin >> s >> t;
  auto start = clock();
  for (int i = 0; i < t; ++i) {
    solve();
    k = 0;
    kmint = Mint{0};
  }
  dbg(tot);
  dbg(tot2);
  dbg(tot3);
  dbg(clock() - start);
}