#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()
using namespace std;
const int BASE_DIGITS = 9, BASE = 1000000000;
struct BigInt {
int sign; vector<int> a;
// Constructors
BigInt() : sign(1) {}
BigInt(long long v) { *this = v; }
BigInt& operator=(long long v) { sign = v < 0 ? -1 : 1; v = v < 0 ? -v : v; a.clear(); while(v > 0) {a.push_back(v % BASE); v /= BASE;} return *this; }
BigInt(const string& s) { read(s); }
// Input/Output
void read(const string& s) { sign = 1; a.clear(); int pos = 0; while(pos < (int)s.size() && (s[pos] == '-' || s[pos] == '+')) { if(s[pos] == '-') sign = -sign; pos++; } for(int i = s.size()-1; i >= pos; i -= BASE_DIGITS) {int x = 0; for(int j = max(pos, i - BASE_DIGITS + 1); j <= i; j++) x = x * 10 + s[j] - '0'; a.push_back(x);} trim(); }
friend istream& operator>>(istream &stream, BigInt &v) { string s; stream >> s; v.read(s); return stream; }
friend ostream& operator<<(ostream &stream, const BigInt &v) { if(v.sign == -1 && !v.isZero()) stream << '-'; stream << (v.a.empty() ? 0 : v.a.back()); for(int i = (int)v.a.size()-2; i >=0; --i) stream << setw(BASE_DIGITS) << setfill('0') << v.a[i]; return stream; }
// Comparison
bool operator<(const BigInt &v) const { if(sign != v.sign) return sign < v.sign; if(a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign; for(int i = a.size()-1; i >=0; i--) if(a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign; return false; }
bool operator>(const BigInt &v) const { return v < *this; }
bool operator<=(const BigInt &v) const { return !(v < *this); }
bool operator>=(const BigInt &v) const { return !(*this < v); }
bool operator==(const BigInt &v) const { return !(*this < v) && !(v < *this); }
bool operator!=(const BigInt &v) const { return *this < v || v < *this; }
friend int __compare_abs(const BigInt& x, const BigInt& y) { if(x.a.size() != y.a.size()) return x.a.size() < y.a.size() ? -1 : 1; for(int i = x.a.size()-1; i >=0; --i) if(x.a[i] != y.a[i]) return x.a[i] < y.a[i] ? -1 : 1; return 0; }
// Unary and Add/Sub
BigInt operator-() const { BigInt res = *this; if(!isZero()) res.sign = -sign; return res; }
void __internal_add(const BigInt& v) { if(a.size() < v.a.size()) a.resize(v.a.size(), 0); int carry = 0; for(int i = 0; i < max(a.size(), v.a.size()) || carry; ++i) { if(i == a.size()) a.push_back(0); a[i] += carry + (i < v.a.size() ? v.a[i] : 0); carry = a[i] >= BASE ? 1 : 0; if(carry) a[i] -= BASE; } }
void __internal_sub(const BigInt& v) { int carry = 0; for(int i = 0; i < v.a.size() || carry; ++i) { a[i] -= carry + (i < v.a.size() ? v.a[i] : 0); carry = a[i] < 0 ? 1 : 0; if(carry) a[i] += BASE; } trim(); }
BigInt operator+=(const BigInt& v) { if(sign == v.sign) { __internal_add(v); } else { if(__compare_abs(*this, v) >= 0) { __internal_sub(v); } else { BigInt vv = v; swap(*this, vv); __internal_sub(vv); } } return *this; }
BigInt operator-=(const BigInt& v) { if(sign == v.sign) { if(__compare_abs(*this, v) >= 0) { __internal_sub(v); } else { BigInt vv = v; swap(*this, vv); __internal_sub(vv); sign = -sign; } } else { __internal_add(v); } return *this; }
template<typename L, typename R>
typename enable_if<is_convertible<L, BigInt>::value && is_convertible<R, BigInt>::value && is_lvalue_reference<R&&>::value, BigInt>::type
friend operator+(L&& l, R&& r) { BigInt result(std::forward<L>(l)); result += r; return result; }
template<typename L, typename R>
typename enable_if<is_convertible<L, BigInt>::value && is_convertible<R, BigInt>::value && is_rvalue_reference<R&&>::value, BigInt>::type
friend operator+(L&& l, R&& r) { BigInt result(std::move(r)); result += l; return result; }
template<typename L, typename R>
typename enable_if<is_convertible<L, BigInt>::value && is_convertible<R, BigInt>::value, BigInt>::type
friend operator-(L&& l, R&& r) { BigInt result(std::forward<L>(l)); result -= r; return result; }
// Multiplication and Division
friend pair<BigInt, BigInt> divmod(const BigInt& a1, const BigInt& b1) { assert(b1 > 0); long long norm = BASE / (b1.a.back() + 1); BigInt a = a1.abs_val() * norm, b = b1.abs_val() * norm, q = 0, r = 0; q.a.resize(a.a.size()); for(int i = a.a.size()-1; i >=0; i--) { r *= BASE; r += a.a[i]; long long s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()]; long long s2 = r.a.size() <= b.a.size()-1 ? 0 : r.a[b.a.size()-1]; long long d = (static_cast<long long>(BASE) * s1 + s2) / b.a.back(); r -= b * d; while(r < 0) { r += b; --d; } q.a[i] = d; } q.sign = a1.sign * b1.sign; r.sign = a1.sign; q.trim(); r.trim(); auto res = make_pair(q, r / norm); if(res.second < 0) res.second += b1; return res; }
BigInt operator/(const BigInt &v) const { return v < 0 ? divmod(-*this, -v).first : divmod(*this, v).first; }
BigInt operator%(const BigInt &v) const { return divmod(*this, v).second; }
void operator/=(int v) { assert(v > 0); if(static_cast<long long>(std::abs(static_cast<long long>(v))) >= BASE) { *this /= BigInt(v); return; } if(v < 0) { sign = -sign; v = -v; } int rem = 0; for(int i = a.size()-1; i >=0; --i) { long long cur = a[i] + static_cast<long long>(rem) * BASE; a[i] = cur / v; rem = cur % v; } trim(); }
BigInt operator/(int v) const { assert(v > 0); if(static_cast<long long>(std::abs(static_cast<long long>(v))) >= BASE) return *this / BigInt(v); BigInt res = *this; res /= v; return res; }
void operator/=(const BigInt &v) { *this = *this / v; }
long long operator%(long long v) const { assert(v > 0 && v < BASE); int m = 0; for(int i = a.size()-1; i >=0; --i) m = (a[i] + static_cast<long long>(m) * BASE) % v; return m * sign; }
void operator*=(int v) { if(static_cast<long long>(std::abs(static_cast<long long>(v))) >= BASE) { *this *= BigInt(v); return; } if(v < 0) { sign = -sign; v = -v; } int carry = 0; for(int i = 0; i < (int)a.size() || carry; ++i) { if(i == a.size()) a.push_back(0); long long cur = static_cast<long long>(a[i]) * v + carry; carry = cur / BASE; a[i] = cur % BASE; } trim(); }
BigInt operator*(int v) const { if(static_cast<long long>(std::abs(static_cast<long long>(v))) >= BASE) return *this * BigInt(v); BigInt res = *this; res *= v; return res; }
// Base Conversion and FFT
static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) { vector<long long> p(max(old_digits, new_digits)+1, 1); for(int i = 1; i < p.size(); i++) p[i] = p[i-1] * 10; vector<int> res; long long cur = 0; int cur_digits = 0; for(auto num : a) { cur += num * p[cur_digits]; cur_digits += old_digits; while(cur_digits >= new_digits) { res.push_back(cur % p[new_digits]); cur /= p[new_digits]; cur_digits -= new_digits; } } res.push_back(static_cast<int>(cur)); while(!res.empty() && !res.back()) res.pop_back(); return res; }
void fft(vector<complex<double>> &x, bool invert_flag) const { int n = x.size(); for(int i =1, j=0; i<n; i++){int bit = n>>1; while(j>=bit){j-=bit; bit>>=1;} j+=bit; if(i<j) swap(x[i], x[j]); } for(int len=2; len<=n; len <<=1){ double ang = 2 * 3.14159265358979323846 / len * (invert_flag ? -1 : 1); complex<double> wlen(cos(ang), sin(ang)); for(int i=0;i<n;i+=len){ complex<double> w(1); for(int j=0; j<len/2; ++j){ complex<double> u = x[i+j], v = x[i+j+len/2] * w; x[i+j] = u + v; x[i+j+len/2] = u - v; w *= wlen; } } } if(invert_flag) for(auto &c : x) c /= n; }
void multiply_fft(const vector<int> &x, const vector<int> &y, vector<int> &res) const { vector<complex<double>> fa(x.begin(), x.end()), fb(y.begin(), y.end()); int n=1; while(n < max(x.size(), y.size())) n <<=1; n <<=1; fa.resize(n); fb.resize(n); fft(fa, false); fft(fb, false); for(int i=0;i<n;i++) fa[i] *= fb[i]; fft(fa, true); res.resize(n); long long carry=0; for(int i=0;i<n;i++) { long long t = round(fa[i].real()) + carry; carry = t / 1000; res[i] = t % 1000; } }
// Multiplication Methods
BigInt mul_simple(const BigInt &v) const { BigInt res; res.sign = sign * v.sign; res.a.resize(a.size() + v.a.size(), 0); for(int i=0;i<a.size();i++) if(a[i]) for(int j=0, carry=0; j < v.a.size() || carry; j++){ long long cur = res.a[i+j] + (static_cast<long long>(a[i]) * (j < v.a.size() ? v.a[j] : 0)) + carry; carry = cur / BASE; res.a[i+j] = cur % BASE; } res.trim(); return res; }
typedef vector<long long> vll;
static vll karatsubaMultiply(const vll &a, const vll &b) { int n=a.size(); vll res(n+n, 0); if(n <=32){ for(int i=0;i<n;i++) for(int j=0;j<n;j++) res[i+j] += a[i] * b[j]; return res; } int k=n>>1; vll a1(a.begin(), a.begin()+k), a2(a.begin()+k, a.end()), b1(b.begin(), b.begin()+k), b2(b.begin()+k, b.end()), a1b1 = karatsubaMultiply(a1, b1), a2b2 = karatsubaMultiply(a2, b2); for(int i=0;i<k;i++) { a2[i] += a1[i]; b2[i] += b1[i]; } vll r = karatsubaMultiply(a2, b2); for(int i=0;i<r.size();i++) res[i+k] += r[i] - (i < a1b1.size() ? a1b1[i] : 0) - (i < a2b2.size() ? a2b2[i] : 0); for(int i=0;i<a1b1.size();i++) res[i] += a1b1[i]; for(int i=0;i<a2b2.size();i++) res[i+n] += a2b2[i]; return res; }
BigInt mul_karatsuba(const BigInt &v) const { vector<int> x6 = convert_base(a, BASE_DIGITS, 6), y6 = convert_base(v.a, BASE_DIGITS, 6); vll x(x6.begin(), x6.end()), y(y6.begin(), y6.end()); while(x.size() < y.size()) x.push_back(0); while(y.size() < x.size()) y.push_back(0); while(x.size() & (x.size()-1)) {x.push_back(0); y.push_back(0);} vll c = karatsubaMultiply(x, y); BigInt res; res.sign = sign * v.sign; long long carry=0; for(auto num : c) { long long cur = num + carry; res.a.push_back(cur % 1000000); carry = cur / 1000000; } res.a = convert_base(res.a, 6, BASE_DIGITS); res.trim(); return res; }
BigInt mul_fft(const BigInt& v) const { BigInt res; res.sign = sign * v.sign; multiply_fft(convert_base(a, BASE_DIGITS, 3), convert_base(v.a, BASE_DIGITS, 3), res.a); res.a = convert_base(res.a, 3, BASE_DIGITS); res.trim(); return res; }
void operator*=(const BigInt &v) { *this = *this * v; }
BigInt operator*(const BigInt &v) const { if(a.size() * v.a.size() <= 1000111) return mul_simple(v); if(a.size() > 500111 || v.a.size() > 500111) return mul_fft(v); return mul_karatsuba(v); }
// Miscellaneous
BigInt abs_val() const { BigInt res = *this; res.sign = 1; return res; }
void trim() { while(!a.empty() && !a.back()) a.pop_back(); if(a.empty()) sign = 1; }
bool isZero() const { return a.empty() || (a.size() == 1 && !a[0]); }
friend BigInt gcd(const BigInt &a, const BigInt &b) { return b.isZero() ? a : gcd(b, a % b); }
friend BigInt lcm(const BigInt &a, const BigInt &b) { return a / gcd(a, b) * b; }
friend BigInt sqrt(const BigInt &a1) { BigInt a = a1; while(a.a.empty() || a.a.size() % 2 == 1) a.a.push_back(0); int n = a.a.size(); int firstDigit = static_cast<int>(sqrt(static_cast<double>(a.a[n-1]) * BASE + a.a[n-2])); int norm = BASE / (firstDigit + 1); a *= norm; a *= norm; while(a.a.empty() || a.a.size() % 2 == 1) a.a.push_back(0); BigInt r = static_cast<long long>(a.a[n-1]) * BASE + a.a[n-2]; firstDigit = static_cast<int>(sqrt(static_cast<double>(a.a[n-1]) * BASE + a.a[n-2])); int q = firstDigit; BigInt res; for(int j = n/2-1; j >=0; j--){ while(1){ BigInt temp = (res * 2 * BigInt(BASE) + q) * q; if(!(r - temp < 0)) { r = r - temp; break; } --q; } res *= BASE; res += q; if(j > 0){ int d1 = res.a.size()+2 < r.a.size() ? r.a[res.a.size()+2] : 0, d2 = res.a.size()+1 < r.a.size() ? r.a[res.a.size()+1] : 0, d3 = res.a.size() < r.a.size() ? r.a[res.a.size()] : 0; q = ((static_cast<long long>(d1) * BASE * BASE + static_cast<long long>(d2) * BASE + d3) / (firstDigit * 2)); } } res.trim(); return res / norm; }
};
const int hv = 1e18;
BigInt b(i128 x) {
int f1 = x%hv;
BigInt r = f1;
x -= f1; x /= hv;
r += BigInt(hv)*BigInt(x);
return r;
}
std::ostream& operator<<(std::ostream& out, __int128 value) { char buffer[40], *ptr = &buffer[39]; *ptr = '\0'; bool neg = value < 0; if (neg) value = -value; do { *--ptr = '0' + (value % 10); value /= 10; } while (value); if (neg) *--ptr = '-'; return out << ptr; }
const i128 inf = 1e38;
const int mxn = 305;
const int mod = 998244353;
int n,m;
BigInt k;
int U[2*mxn],V[2*mxn],W[2*mxn]; //edges
i128 cyc[mxn][mxn];
i128 dist[mxn][mxn];
i128 d1[2*mxn*mxn][mxn];
BigInt dp[mxn*mxn][mxn];
BigInt MIN(BigInt a, BigInt b) {
if (a==BigInt(-1)) return b;
if (b==BigInt(-1)) return a;
return (a<b ? a : b);
}
void solve() {
cin>>n>>m>>k;
for (int i=0; i<m; i++) {
cin>>U[i]>>V[i]>>W[i];
--U[i]; --V[i];
}
for (int cs=0; cs<n; cs++) {
for (int i=0; i<=n; i++) {
for (int j=0; j<n; j++) {
dist[i][j] = inf;
}
}
dist[0][cs] = 0;
for (int i=1; i<=n; i++) {
for (int ne=0; ne<m; ne++) {
dist[i][V[ne]] = min(dist[i][V[ne]],dist[i-1][U[ne]]+W[ne]);
}
cyc[cs][i] = dist[i][cs];
}
}
for (int i=0; i<2*n*n+5; i++) {
for (int j=0; j<n; j++) {
d1[i][j] = inf;
}
}
d1[0][0] = 0;
for (int i=1; i<2*n*n+5; i++) {
for (int ne=0; ne<m; ne++) {
d1[i][V[ne]] = min(d1[i][V[ne]],d1[i-1][U[ne]]+W[ne]);
}
}
if (k <= BigInt(n*n*2)) {
int kv = k%((int)(1e8));
for (int i=0; i<n; i++) {
cout<<(d1[kv][i]==inf?(i128)-1:d1[kv][i]%mod)<<" ";
}
cout<<"\n";
return;
}
for (int i=0; i<=n*n+5; i++) {
for (int j=0; j<n; j++) {
dp[i][j] = -1;
}
}
for (int i=0; i<n; i++) {
i128 dd = d1[n*n][i];
if (dd==inf) continue;
for (int cl=1; cl<=n; cl++) {
if (cyc[i][cl]==inf) continue;
BigInt rem = k-BigInt(2*n*n-n);
BigInt amt = rem/cl;
int residue = rem%cl;
BigInt val = b(dd)+b(cyc[i][cl])*amt;
assert(residue <= n*n+5);
dp[residue+n*n-n][i] = MIN(dp[residue+n*n-n][i], val);
}
}
for (int cd = n*n+4; cd >= 0; cd--) {
for (int ne=0; ne<m; ne++) {
if (dp[cd+1][U[ne]] == BigInt(-1)) continue;
dp[cd][V[ne]] = MIN(dp[cd][V[ne]],dp[cd+1][U[ne]]+BigInt(W[ne]));
}
}
for (int i=0; i<n; i++) {
cout<<(dp[0][i])%mod<<" ";
}
cout<<"\n";
}
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int s,t; cin>>s>>t;
while (t--) {
solve();
}
return 0;
}