#include<cstdio>
#include<algorithm>
const int N=303,M=603,Vm=90003,mod=998244353;
typedef long long ll;const ll Mod=mod;
typedef __int128 LL;const LL inf=1e37;
//typedef ll LL;const LL inf=1e18;
char sk[107];int U[M],V[M],n,m;ll W[M];
struct frc{LL vl;int c;};
inline bool operator<(const frc&x,const frc&y){return x.vl*y.c<y.vl*x.c;}
inline bool operator==(const frc&x,const frc&y){return x.vl*y.c==y.vl*x.c;}
template<class T>inline void ckmn(T&a,const T&b){if(b<a)a=b;}
LL f[N][N],tmpr[N][N];
frc disr[N];int modv[N];
LL readmx(char*s,LL mx){LL ans=0;for(;*s;++s)ans=std::min(ans*10+((*s)^48),inf);return ans;}
ll readmod(char*s,ll mod){ll ans=0;for(;*s;++s)ans=(ans*10+((*s)^48))%mod;return ans;}
void chkr(int u,int t){if(tmpr[t][u]<inf)ckmn(disr[u],(frc){tmpr[t][u],t});}
struct pii{LL A,vl;int c;};LL K;pii g[N][N];
inline pii addp(const pii&a,ll b){return {a.A,a.vl+(LL)b*a.c,a.c};}
inline bool operator<(const pii&x,const pii&y)
{
	LL va=x.A*y.c-y.A*x.c,vb=y.vl*x.c-x.vl*y.c;
	if(!va)return vb>0;
	if(va>0)
	{
		if(vb<=0||K==inf)return 0;
		return K<=(vb-1)/va;
	}
	va=-va;vb=-vb;
	if(vb<=0||K==inf)return 1;
	return K>vb/va;
}
int main()
{
//	freopen("huant.in","r",stdin);
//	freopen("huan.out","w",stdout);
	int T;scanf("%*d%d",&T);
	while(T--)
	{
		scanf("%d%d%s",&n,&m,sk);K=readmx(sk,inf);
		for(int i=1;i<=m;++i)scanf("%d%d%lld",U+i,V+i,W+i);
		
		int mx=n*n;if(K<=mx+mx)mx=K;
		
		f[0][1]=0;for(int i=2;i<=n;++i)f[0][i]=inf;
		for(int i=1;i<=mx;++i)
		{
			LL*cur=f[i%n],*las=f[(i-1)%n];std::fill(cur+1,cur+n+1,inf);
			for(int j=1;j<=m;++j)ckmn(cur[V[j]],las[U[j]]+W[j]);
		}
		
		if(K==mx){for(int i=1;i<=n;++i)printf("%d ",f[mx%n][i]<inf?(int)(f[mx%n][i]%mod):-1);puts("");continue;}
		
		#define prt(x) (ll)((x)/(LL)1e18),(ll)((x)%(LL)1e18)
		for(int u=1;u<=n;++u)
		{
			disr[u]={1,0};
			std::fill(tmpr[1]+1,tmpr[1]+n+1,inf);
			for(int j=1;j<=m;++j)if(U[j]==u)ckmn<LL>(tmpr[1][V[j]],W[j]);
			chkr(u,1);
			for(int i=2;i<=n;++i)
			{
				std::fill(tmpr[i]+1,tmpr[i]+n+1,inf);
				for(int j=1;j<=m;++j)ckmn(tmpr[i][V[j]],tmpr[i-1][U[j]]+W[j]);
				chkr(u,i);
			}
		}
		
		for(int i=1;i<=n;++i)modv[i]=readmod(sk,i);
		
		for(int i=0;i<n;++i)std::fill(g[i]+1,g[i]+n+1,(pii){1,0,0});
		for(int u=1;u<=n;++u)if(disr[u].c)
		{
			const int r=disr[u].c;
//			printf("u=%d r=%d\n",u,r);
			for(int ii=0;ii<n;++ii)if(f[(n-ii)%n][u]<inf)
			{
				int jj=-(modv[r]-2*n*n+ii)%r;if(jj<0)jj+=r;
				LL disii=f[(n-ii)%n][u],vfs=disii*r-(2*n*n-ii-jj)*disr[u].vl;
				ckmn(g[(n-jj)%n][u],(pii){disr[u].vl,vfs,r});
//				printf("u=%d ii=%d jj=%d disr=%lld|%018lld r=%d\n",u,ii,jj,prt(disr[u].vl),r);
			}
		}
		
		for(int i=n*n-1;~i;--i)
		{
			pii*cur=g[i%n],*las=g[(i+1)%n];
			if(i<=n*n-n)std::fill(cur+1,cur+n+1,(pii){1,0,0});
			for(int j=1;j<=m;++j)ckmn(cur[V[j]],addp(las[U[j]],W[j]));
		}
		
		for(int i=1;i<=n;++i)
			if(!g[0][i].c)printf("-1 ");
			else
			{
				const int r=g[0][i].c;
//				printf("g[0][i].vl=%lld|%018lld\n",prt(g[0][i].vl));
				ll mmod=Mod*r,avl=g[0][i].A%mmod;
//				printf("avlt=%lld|%018lld\n",prt(g[0][i].A));
				int ans=(((LL)readmod(sk,mmod)*avl+g[0][i].vl)%mmod)/r;
				printf("%d ",ans);
			}
		puts("");
	}
	return 0;
}