/**
 * @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

using i128 = __int128_t;

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

constexpr int MOD = 998'244'353;

using i128 = __int128_t;

template <class T>
concept integral = std::integral<T> || std::is_same_v<i128, T>;
// based on https://cp-algorithms.com/algebra/big-integer.html
struct BigInt {
  static constexpr int LG = 9;
  static constexpr int BASE = []() -> int {
    int ans = 1;
    for (int i = 0; i < LG; ++i) {
      ans *= 10;
    }
    return ans;
  }();
  std::vector<int> a;
  BigInt() = default;
  explicit BigInt(integral auto val) {
    while (val > 0) {
      a.push_back(static_cast<int>(val % BASE));
      val /= BASE;
    }
  }
  explicit BigInt(const std::string &s) {
    for (int i = static_cast<int>(s.size()) - 1; i >= 0; i -= BASE) {
      if (i < LG) {
        a.push_back(std::stoi(s.substr(0, i + 1)));
      } else {
        a.push_back(std::stoi(s.substr(i - LG + 1, LG)));
      }
    }
  }
  friend std::istream &operator>>(std::istream &in, BigInt &val) {
    std::string s;
    in >> s;
    val = BigInt{s};
    return in;
  }
  friend std::ostream &operator<<(std::ostream &out, const BigInt &val) {
    for (int i : val.a | rv::reverse) {
      out << i;
    }
    return out;
  }
  void trim() {
    while (!a.empty() && a.back() == 0) {
      a.pop_back();
    }
  }
  BigInt &operator+=(const BigInt &rhs) {
    int carry = 0;
    for (int i = 0; i < std::max(std::ssize(a), std::ssize(rhs.a)); ++i) {
      if (i == std::ssize(a)) {
        a.push_back(0);
      }
      a[i] += carry + (i < std::ssize(rhs.a) ? rhs.a[i] : 0);
      carry = (a[i] >= BASE) ? 1 : 0;
      if (a[i] >= BASE) {
        a[i] -= BASE;
      }
    }
    return *this;
  }
  BigInt &operator-=(const BigInt &rhs) {
    int carry = 0;
    for (int i = 0; i < std::ssize(rhs.a) || carry > 0; ++i) {
      a[i] -= carry + (i < std::ssize(rhs.a) ? rhs.a[i] : 0);
      carry = (a[i] < 0) ? 1 : 0;
      if (a[i] < 0) {
        a[i] += BASE;
      }
    }
    trim();
    return *this;
  }
  BigInt &operator*=(int rhs) {
    assert(rhs < BASE);
    int carry = 0;
    for (int i = 0; i < std::ssize(a) || carry > 0; ++i) {
      if (i == std::ssize(a)) {
        a.push_back(0);
      }
      int64_t cur = carry + int64_t{a[i]} * rhs;
      a[i] = static_cast<int>(cur % BASE);
      carry = static_cast<int>(cur / BASE);
    }
    return *this;
  }
  friend BigInt operator*(const BigInt &lhs, const BigInt &rhs) {
    BigInt ans;
    ans.a.resize(lhs.a.size() + rhs.a.size());
    for (int i = 0; i < std::ssize(lhs.a); ++i) {
      for (int j = 0, carry = 0; j < std::ssize(rhs.a) || carry > 0; ++j) {
        int64_t cur = ans.a[i + j]
          + int64_t{lhs.a[i]} * (j < std::ssize(rhs.a) ? rhs.a[j] : 0) + carry;
        ans.a[i + j] = static_cast<int>(cur % BASE);
        carry = static_cast<int>(cur / BASE);
      }
    }
    ans.trim();
    return ans;
  }
  BigInt &operator*=(const BigInt &rhs) { return *this = *this * rhs; }
  int div_mod(int rhs) {
    int carry = 0;
    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
      int64_t cur = a[i] + int64_t{carry} * BASE;
      a[i] = static_cast<int>(cur / rhs);
      carry = static_cast<int>(cur % rhs);
    }
    trim();
    return carry;
  }
  BigInt &operator/=(int rhs) {
    div_mod(rhs);
    return *this;
  }
  int operator%(int rhs) {
    int carry = 0;
    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
      carry = static_cast<int>((a[i] + int64_t{carry} * BASE) % rhs);
    }
    return carry;
  }
  bool operator==(const BigInt &rhs) const = default;
  bool operator!=(const BigInt &rhs) const = default;
  auto operator<=>(const BigInt &rhs) const {
    if (a.size() != rhs.a.size()) {
      return a.size() <=> rhs.a.size();
    }
    for (int i = static_cast<int>(a.size()) - 1; i >= 0; --i) {
      if (a[i] != rhs.a[i]) {
        return a[i] <=> rhs.a[i];
      }
    }
    return std::strong_ordering::equal;
  }
};
BigInt operator+(BigInt a, const BigInt &b) { return a += b; }
BigInt operator-(BigInt a, const BigInt &b) { return a -= b; }
BigInt operator*(BigInt a, int b) { return a *= b; }
BigInt operator*(int b, BigInt a) { return a *= b; }

#if defined(LOCAL) && __cplusplus >= 202302L
template <> struct std::formatter<BigInt, char> {
  std::formatter<std::string, 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 BigInt &val, FormatContext &ctx) const {
    return underlying.format(std::stringstream{} << val, ctx);
  }
};
#endif

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;
};

clock_t tot = 0;
clock_t tot2 = 0;
clock_t tot3 = 0;

void solve() {
  static_assert(integral<i128>);
  int n, m;
  std::string sk;
  std::cin >> n >> m >> sk;
  BigInt k(sk);

  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(10 * n * n + 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 <= 10 * n * n; ++i) {
    for (auto &[u, v, w] : edges) {
      d0[i][v] = std::min(d0[i][v], d0[i - 1][u] + w);
    }
  }
  if (k <= BigInt{10 * n * n}) {
    int kk = std::stoi(sk);
    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(n * n + 1, std::vector<BigInt>(n));
  std::vector isinf(n * n + 1, std::vector<bool>(n, true));
  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 = n * n - n; j <= n * n; ++j) {
      if (d0[j][i] == INF<i128>) {
        continue;
      }
      BigInt times = k;
      int rem = (times - BigInt{j + n * n}).div_mod(sz);
      int rest = n * n;
      if (rem > 0) {
        times += BigInt{1};
        rest -= sz - rem;
      }
      BigInt res = times * BigInt{mi} + BigInt{d0[j][i]};
      if (isinf[rest][i]) {
        dp[rest][i] = res;
      } else {
        dp[rest][i] = std::min(dp[rest][i], res);
      }
      isinf[rest][i] = false;
    }
  }
  std::vector<std::tuple<int, int, BigInt>> edges2;
  edges2.reserve(edges.size());
  for (auto [u, v, w] : edges) {
    edges2.emplace_back(u, v, w);
  }
  for (int i = n * n - 1; i >= 0; --i) {
    for (const auto &[u, v, w] : edges2) {
      if (!isinf[i + 1][u]) {
        if (isinf[i][v]) {
          dp[i][v] = dp[i + 1][u] + w;
        } else {
          dp[i][v] = std::min(dp[i][v], dp[i + 1][u] + w);
        }
        isinf[i][v] = false;
      }
    }
  }
  for (int i = 0; i < n; ++i) {
    if (isinf[0][i]) {
      std::cout << "-1 ";
    } else {
      std::cout << dp[0][i] % MOD << ' ';
    }
  }
  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;
  for (int i = 0; i < t; ++i) {
    solve();
  }
}