#pragma GCC optimize("trapv")
#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])<<" ";
        }
        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 = BigInt(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;
}