#pragma GCC optimize("O3,unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#define i32 int32_t
#define int int64_t
#define i128 __int128_t
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

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

struct bigint {
	static const int B = 1e18;
	static const int L = 5;
	i128 v[L];
	bigint() {memset(v,0,sizeof(v));}
	bigint(int val) {memset(v,0,sizeof(v));v[0] = val;propogate();}
	bigint(i128 val) {memset(v,0,sizeof(v));v[0] = val;		}
    bigint(const string& s) {memset(v, 0, sizeof(v));int n = s.size();int chunkSize = 18;for (int i = 0; i < n; i += chunkSize) {    int end = n - i;    int start = max((int)0, end - chunkSize);    string part = s.substr(start, end - start);    int chunk = stoll(part);    v[(i/chunkSize)] = chunk;}propogate();}
	void propogate() {for (int i=0; i<L-1; i++) {v[i+1] += v[i]/B;v[i] %= B;}}
	void add(i128 a) {v[0] += a;propogate();}
	void add(bigint b) {for (int i=0; i<L; i++) {v[i] += b.v[i];}propogate();}
	int borrowable() {	for (int i=1; i<L; i++) {if (v[i]) return 1;}	return 0;}
	void borrow(int i) {	if (!v[i+1]) borrow(v[i+1]);	v[i+1]--;	v[i] += B;}
	void subtract(int a) {	if (v[0] < a) {borrow(0);}	v[0] -= a; assert(v[0]>=0);propogate();}
	void multiply(i128 a) {	for (int i=0; i<L; i++) {v[i] *= a;}	propogate();}
	void divide(int a) {	for (int i=L-1; i>=0; i--) {		if (i) v[i-1] += B*(v[i]%a);		v[i] /= a;	}	propogate();}
	void setmin(bigint b) {	int g = 1;	for (int i=L-1; i>=0; i--) {		if (v[i] < b.v[i]) {g = 0; break;}		else if (v[i] > b.v[i]) break;	}	if (!g) return;	for (int i=L-1; i>=0; i--) {		v[i] = b.v[i];	}}
	bool lesser(i128 V) {	for (int i=1; i<L; i++) {if (v[i]) return 0;}	return (v[0]<=V);}
	void setinf() {for (int i=0; i<L; i++) {v[i] = B-1;}}
	void copy(bigint b) {for (int i=0; i<L; i++) {v[i] = b.v[i];}}
	int remainder(int d) {	i128 cr=0;	for (int i=L-1; i>=0; i--) {		cr *= B;		cr += v[i];		cr %= d;	}	return (int)cr;}
	int isinf() {	for (int i=0; i<L; i++) {		if (v[i]!=B-1) return 0;	}	return 1;}
	void print() {
	    int i = L - 1;
	    while (i > 0 && v[i] == 0) i--;
	    cout<<v[i];
	    for (i--; i >= 0; i--) {
	        cout<<setw(18)<<setfill('0')<<v[i];
	    }
	}
};

const int hv = 1e18;

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[2][mxn];
vector<pair<bigint,int>> update[mxn*mxn];

void solve() {
    cin>>n>>m;
    string KTT; cin>>KTT;
    k = bigint(KTT);
    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.lesser(n*n*2)) {
        int kv = k.v[0];
        for (int i=0; i<n; i++) {
            cout<<(d1[kv][i]==inf?(i128)-1:d1[kv][i]%mod)<<" ";
        }
        cout<<"\n";
        return;
    }
    
    k.subtract(2*n*n-n);
	
	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 amt; amt.copy(k);
			amt.divide(cl);
			int residue = k.remainder(cl);
			amt.multiply(cyc[i][cl]);
			amt.add(dd);
			update[residue+n*n-n].push_back({amt,i});
//			amt.print();
//			cout<<"\n";
		}
	}

	bigint temp;
	
	int cp=0,pp=1;
	
	for (int i=0; i<2; i++) {
		for (int j=0; j<n; j++) {
			dp[i][j].setinf();
		}
	}
	
	for (int cd = n*n+4; cd >= 0; cd--) {
		
		swap(cp,pp);
		for (int i=0; i<mxn; i++) {
			dp[cp][i].setinf();
		}
		for (auto [val,ind] : update[cd]) {
			dp[cp][ind].setmin(val);
		}
		for (int ne=0; ne<m; ne++) {
			if (dp[pp][U[ne]].isinf()) continue;
			temp.copy(dp[pp][U[ne]]);
			temp.add(W[ne]);
			dp[cp][V[ne]].setmin(temp);// = MIN(dp[cd][V[ne]],dp[cd+1][U[ne]]+BigInt(W[ne]));
		}
	}
	
	for (int i=0; i<n; i++) {
		if (dp[cp][i].isinf()) cout<<"-1 ";
		else cout<<dp[cp][i].remainder(mod)<<" ";
	}
	cout<<"\n";
}

/*
slow multiplcation ok
slow division ok
fast addition, comparison ... easy
*/

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	int s,t; cin>>s>>t;
	while (t--) {
		solve();
	}
	
	return 0;
}