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

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[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;
    }
	
	for (int i=0; i<=n*n+5; i++) {
		for (int j=0; j<n; j++) {
			dp[i][j].setinf();
		}
	}

	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);
			dp[residue+n*n-n][i].setmin(amt);
		}
	}
	bigint temp;
	for (int cd = n*n+4; cd >= 0; cd--) {
		for (int ne=0; ne<m; ne++) {
			if (dp[cd+1][U[ne]].isinf()) continue;
			temp.copy(dp[cd+1][U[ne]]);
			temp.add(W[ne]);
			dp[cd][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[0][i].isinf()) cout<<"-1 ";
		else cout<<dp[0][i].remainder(mod)<<" ";
	}
}

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