#pragma GCC optimize("Ofast", "unroll-loops")
#include<bits/stdc++.h>
using namespace std; using ll = long long;
#define For(i, j, k) for ( int i = (j) ; i <= (k) ; i++ )
#define Fol(i, j, k) for ( int i = (j) ; i >= (k) ; i-- )
inline ostream &operator<<(ostream &os, __int128 x) { if ( x == (__int128)1 << 100 ) return os << "inf"; static char b[40]; int d = 0; do b[d++] = ( x % 10 ) | 48, x /= 10; while ( x ); do os << b[--d]; while ( d ); return os; }
constexpr int mod = 998244353;
inline void add(int &x) { x >= mod && ( x -= mod ); }
inline void sub(int &x) { x < 0 && ( x += mod ); }
inline int qpow(int x, int y) { int z = 1; while ( y ) { if ( y & 1 ) z = (ll)z * x % mod; if ( y >>= 1 ) x = (ll)x * x % mod; } return z; }
inline int inv(int x) { return qpow(x, mod - 2); }
constexpr __int128 inf = (__int128)1 << 100;
int n, m, kk, u[609], v[609]; ll w[609]; string sk;
namespace small
{
	__int128 f0[309], f1[309];
	inline void work()
	{
		fill(f1 + 2, f1 + n + 1, inf), f1[1] = 0;
		For(i, 1, kk)
		{
			copy(f1 + 1, f1 + n + 1, f0 + 1), fill(f1 + 1, f1 + n + 1, inf);
			For(j, 1, m) f1[v[j]] = min(f1[v[j]], f0[u[j]] + w[j]);
		}
		For(i, 1, n) cout << ( f1[i] == inf ? -1 : (int)( f1[i] % mod ) ) << " \n"[i == n];
	}
}
namespace big
{
	int rm[309], o; __int128 ff0[309][309], ff1[309][309], f0[309], f1[309], kkk;
	struct F
	{
		__int128 x; int y;
		inline F() {}
		inline F(__int128 x, int y) : x(x), y(y) {}
		inline bool operator<(const F &o)const { return x * o.y < o.x * y; }
	}	r[309];
	struct G
	{
		__int128 x, y; int z;
		inline G() {}
		inline G(__int128 x, __int128 y, int z) : x(x), y(y), z(z) {}
		inline int val()const { return ( x % mod * kk + y % mod ) * inv(z) % mod; }
		inline G operator+(__int128 o)const { return G(x, y + o * z, z); }
		inline bool operator<(const G &o)const
		{
			__int128 p = x * o.z, q = o.x * z;
			if ( p == q ) return y * o.z < o.y * z;
			if ( (int)sk.size() > 31 ) return p < q;
			__int128 d = p - q;
			if ( ( d > 0 ? d : -d ) > inf * 10 / kkk ) return p < q;
			return d * kkk + y * o.z < o.y * z;
		}
	}	g0[309], g1[309]; vector < pair < int, G > > vec[90009];
	inline void slv()
	{
		if ( (int)sk.size() <= 31 ) { kkk = 0; for ( char c : sk ) kkk = kkk * 10 + ( c ^ '0' ); }
		kk = 0; for ( char c : sk ) kk = ( kk * 10ll + ( c ^ '0' ) ) % mod;
		For(i, 1, n)
		{
			rm[i] = 0; for ( char c : sk ) rm[i] = ( rm[i] * 10 + ( c ^ '0' ) ) % i;
			( rm[i] -= 2 * n * n % i ) < 0 && ( rm[i] += i );
		}
		For(i, 1, n) fill(ff1[i] + 1, ff1[i] + n + 1, inf), ff1[i][i] = 0, r[i] = F(inf, 1);
		For(i, 1, n)
		{
			For(j, 1, n) copy(ff1[j] + 1, ff1[j] + n + 1, ff0[j] + 1), fill(ff1[j] + 1, ff1[j] + n + 1, inf);
			For(j, 1, n) For(k, 1, m) ff1[j][v[k]] = min(ff1[j][v[k]], ff0[j][u[k]] + w[k]);
			For(j, 1, n) if ( ff1[j][j] != inf ) r[j] = min(r[j], F(ff1[j][j], i));
		}
		fill(f1 + 2, f1 + n + 1, inf), f1[1] = 0;
		For(i, n * n - n + 1, n * n) vec[i].clear();
		For(i, 1, n * n)
		{
			copy(f1 + 1, f1 + n + 1, f0 + 1), fill(f1 + 1, f1 + n + 1, inf);
			For(j, 1, m) f1[v[j]] = min(f1[v[j]], f0[u[j]] + w[j]);
			if ( i > n * n - n ) For(j, 1, n) if ( f1[j] != inf && r[j].x != inf )
			{
				o = ( rm[r[j].y] + n * n - i ) % r[j].y, o = n * n - ( o ? r[j].y - o : 0 );
				vec[o].emplace_back(j, G(r[j].x, f1[j] * r[j].y - ( i + o ) * r[j].x, r[j].y));
			}
		}
		fill(g1 + 1, g1 + n + 1, G(inf, inf, 1));
		Fol(i, n * n, 0)
		{
			copy(g1 + 1, g1 + n + 1, g0 + 1), fill(g1 + 1, g1 + n + 1, G(inf, inf, 1));
			if ( i > n * n - n ) for ( auto _ : vec[i] ) g1[_.first] = min(g1[_.first], _.second);
			For(j, 1, m) g1[v[j]] = min(g1[v[j]], g0[u[j]] + w[j]);
		}
		For(i, 1, n) cout << ( g1[i].x == inf && g1[i].y == inf ? -1 : g1[i].val() ) << " \n"[i == n];
	}
}
inline void work()
{
	cin >> n >> m >> sk;
	For(i, 1, m) cin >> u[i] >> v[i] >> w[i];
	(int)sk.size() < 7 && ( kk = stoi(sk) ) <= 2 * n * n ? small::work() : big::slv();
}
int main()
{
	// freopen("huan.in", "r", stdin), freopen("huan.out", "w", stdout);
	cin.tie(nullptr) -> sync_with_stdio(false);
	int _, t; cin >> _ >> t; while ( t-- ) work(); return 0;
}