#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(0LL, 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 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];
}
}
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][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;
}