#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
//	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
#define mod 998244353
#define ull __int128
ll t,n,m,d[330];
ull K,inf=1,f[303][303],g[303][303],h[303][2];
char s[110];
struct edge{
	ll u,v,w;
}e[660];
struct node{
	ull a,b;
	ll k;
}dp[303][303];
il bl operator<(const node &x,const node &y){
	if(!x.k) return 0;
	if(!y.k) return 1;
	ull A1=x.a*y.k,B1=x.b*y.k,A2=y.a*x.k,B2=y.b*x.k;
	A1+=B1/K;
	B1%=K;
	A2+=B2/K;
	B2%=K;
	if(A1==A2) return B1<B2;
	return A1<A2;
}
il node operator+(const node &x,const ll &y){
	node res=x;
	res.b+=(ull)res.k*y;
	res.a+=res.b/K;
	res.b%=K;
	return res;
}
il void solve1(ll lim){
	fr(i,0,n) fr(j,1,n) f[i][j]=inf;
	f[0][1]=0;
	fr(k,1,lim){
		ll o=k%(n+1),oo=(k-1)%(n+1);
		fr(i,1,n) f[o][i]=inf;
		fr(i,1,m){
			ll u=e[i].u,v=e[i].v;
			if(f[oo][u]<inf) f[o][v]=min(f[o][v],f[oo][u]+e[i].w);
		}
	}
}
il void solve2(ll S){
	fr(i,0,n) fr(j,1,n) g[i][j]=inf;
	g[0][S]=0;
	h[S][0]=1;
	fr(k,1,n){
		fr(i,1,m){
			ll u=e[i].u,v=e[i].v;
			if(g[k-1][u]<inf) g[k][v]=min(g[k][v],g[k-1][u]+e[i].w);
		}
		if(g[k][S]!=inf&&g[k][S]*h[S][1]<h[S][0]*k){
			h[S][0]=g[k][S];
			h[S][1]=k;
		}
	}
}
il void solve3(){
	pfr(k,n*n-1,0){
		ll o=k%(n+1),oo=(k+1)%(n+1);
		if(k<=n*(n-1)){
			fr(i,1,n) dp[o][i]=(node){0,0,0};
		}
		fr(i,1,m){
			ll u=e[i].u,v=e[i].v;
			if(dp[oo][u].k) dp[o][v]=min(dp[o][v],dp[oo][u]+e[i].w);
		}
	}
}
il void clr(){
	fr(i,1,n) d[i]=0;
	fr(i,0,n) fr(j,1,n) dp[i][j]=(node){0,0,0};
	K=0;
	fr(i,1,n) h[i][0]=h[i][1]=0;
}
int main(){
	fr(i,1,120) inf*=2;
	t=read(); 
	t=read();
	while(t--){
		n=read();
		m=read();
		scanf("%s",s+1);
		fr(i,1,m){
			e[i].u=read();
			e[i].v=read();
			e[i].w=read();
		}
		ll len=strlen(s+1);
		fr(i,1,len){
			K=min(inf,K*10+(s[i]-'0'));
			fr(j,1,n) d[j]=(d[j]*10+(s[i]-'0'))%j;
		}
		if(K<=2*n*n){
			solve1(K);
			fr(i,1,n){
				if(f[K%(n+1)][i]==inf) writesp(-1);
				else writesp(f[K%(n+1)][i]%mod);
			}
			enter;
			clr();
			continue;
		}
		solve1(n*n);
		fr(i,1,n) solve2(i);
		fr(i,n*n-n+1,n*n){
			fr(u,1,n){
				if(!h[u][1]||f[i%(n+1)][u]==inf) continue;
				ll k=h[u][1],nd=(k-(d[k]-i-n*n)%k)%k;
				ull A=h[u][0],B=h[u][0]*(nd-i-n*n)+f[i%(n+1)][u]*k;
				A+=B/K;
				B%=K;
				if(B<0){
					A--;
					B+=K;
				}
				dp[(n*n-nd)%(n+1)][u]=min(dp[(n*n-nd)%(n+1)][u],(node){A,B,k});
			}
		}
		solve3();
		ll tmp=0;
		fr(i,1,len) tmp=(tmp*10+s[i]-'0')%mod;
		fr(i,1,n){
			if(!dp[0][i].k) writesp(-1);
			else writesp((dp[0][i].a%mod*tmp%mod+dp[0][i].b%mod)*inv(dp[0][i].k,mod)%mod);
		}
		enter;
		clr();
	}
}
/*
1
5 5 101
1 2 1
2 3 100
3 4 10000
4 2 1000000
2 5 10
ans:
-1 -1 33333401 -1 33333311 
*/