#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<ctime>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<bitset>
#include<cassert>
#include<random>
#define sqr(x) ((x)*(x))
#define fz1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define fd1(i,n) for ((i)=(n);(i)>=1;(i)--)
#define fz0g(i,n) for ((i)=0;(i)<=(n);(i)++)
#define fd0g(i,n) for ((i)=(n);(i)>=0;(i)--)
#define fz0k(i,n) for ((i)=0;(i)<(n);(i)++)
#define fd0k(i,n) for ((i)=(((long long)(n))-1);(i)>=0;(i)--)
#define fz(i,x,y) for ((i)=(x);(i)<=(y);(i)++)
#define fd(i,y,x) for ((i)=(y);(i)>=(x);(i)--)
#define fzin fz1(i,n)
#define fzim fz1(i,m)
#define fzjn fz1(j,n)
#define fzjm fz1(j,m)
#define ff(c,itr) for (__typeof((c).begin()) itr=(c).begin();itr!=(c).end();++itr)
#define pb push_back
#define mk make_pair
#define rdst(st,len){static char ss[len];scanf(" %s",ss);(st)=ss;}
#define spln(i,n) (i==n?'\n':' ')
#define fac_init(n){fac[0]=fac[1]=inv[1]=fi[0]=fi[1]=1;fz(i,2,n){fac[i]=1ll*fac[i-1]*i%mod;inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;fi[i]=1ll*fi[i-1]*inv[i]%mod;}}
using namespace std;
typedef long long i64;
typedef long double f80;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef __int128 i128;
inline void read(int &x)
{
	char c;int f=1;
	while(!isdigit(c=getchar()))if(c=='-')f=-1;
	x=(c&15);while(isdigit(c=getchar()))x=(x<<1)+(x<<3)+(c&15);
	x*=f;
}
const int mod=998244353;
int qp(int x,int y){int z=1;while(y){if(y&1){z=1ll*z*x%mod;}x=1ll*x*x%mod;y/=2;}return z;}
const i128 inf=(i128)0x3f3f3f3f3f3f3f3fll*0x3f3f3f3f3f3f3f3fll;
int _,n,m,len,i,j,k;
i128 ck;int dk[305],ek;
string sk;
i128 f[180005][305],g[305][305][305];
int px[605],py[605];i64 pz[605];
struct solar
{
	i128 a,b;
	i64 c;
}h[513][305];
solar add(solar a,i64 b)
{
	a.b+=(i128)a.c*b;
	return a;
}
bool operator <(solar a,solar b)
{
	if(a.c==0) return 0;
	if(b.c==0) return 1;
//	return (a.a*ck+a.b)*b.c<(b.a*ck+b.b)*a.c;
	i128 aa=a.a*b.c,ab=a.b*b.c;
	i128 ba=b.a*a.c,bb=b.b*a.c;
//	cerr<<(double)ab<<' '<<(double)bb<<endl;
	ba-=aa;bb-=ab;
	if(ba==0) return bb>0;
	if(ba>0&&bb>0) return 0;
	if(ba>0) return ((-bb)+ba)/ba<=ck;
	if(bb<=0) return 0;
	return ((bb-1)/(-ba))>=ck;
//	return (a.a*ck+a.b)/a.c<(b.a*ck+b.b)/b.c;
}
bool flg;
void solve()
{
	cin>>n>>m>>sk;ck=ek=0;fz1(i,n)dk[i]=0;
	fz0k(i,sk.size()){
		ck=min(inf,min(ck*2,inf)*5+(sk[i]&15));
		fz1(j,n){
			dk[j]=(dk[j]*10+(sk[i]&15))%j;
		}
		ek=(10ll*ek+(sk[i]&15))%mod;
	}
	fz1(i,m){
		int x,y;i64 z;cin>>x>>y>>z;
		px[i]=x;py[i]=y;pz[i]=z;
	}
	len=n*n/2;
	fz0g(i,len+3)fz1(j,n)f[i][j]=inf;f[0][1]=0;
	if(ck<=n*n*6){
		fz0k(i,ck){
			fz1(j,n)f[(i+1)&1][j]=inf;
			fz1(j,m)f[(i+1)&1][py[j]]=min(f[(i+1)&1][py[j]],f[i&1][px[j]]+pz[j]);
		}
		fz1(i,n){
			if(f[ck&1][i]>=inf) printf("-1"); else printf("%d",(int)(f[ck&1][i]%mod));
			printf(" ",spln(i,n));
		}
		puts("");
		return;
	}
	fz0k(i,len){
		fz1(j,m)f[i+1][py[j]]=min(f[i+1][py[j]],f[i][px[j]]+pz[j]);
	}
	fz0g(i,n)fz0g(j,n)fz0g(k,n)g[i][j][k]=inf;
	fz1(i,n){
		g[i][0][i]=0;
		fz0k(j,n){
			fz1(k,m) g[i][j+1][py[k]]=min(g[i][j+1][py[k]],g[i][j][px[k]]+pz[k]);
		}
	}
	fz0g(i,min(512,len+3))memset(h[i],0,sizeof(h[i]));
//	return;
	fz(i,len-n,len){
		fz1(j,n)if(f[i][j]<inf){
//			cerr<<i<<' '<<j<<endl;
			fz1(k,n){
				if(g[j][k][j]>=inf) continue;
				int tar=(len-n)+((dk[k]-i-(len-n))%k+k)%k;
				assert((i+tar)%k==dk[k]);
				solar tmp;
				tmp.c=k;
				tmp.b=k*f[i][j];
				tmp.b-=(i+tar)*g[j][k][j];
				tmp.a=g[j][k][j];
//				cerr<<i<<' '<<j<<' '<<(int)f[i][j]<<' '<<k<<' '<<tar<<' '<<(int)g[j][k][j]<<' '<<(int)tmp.a<<' '<<(int)tmp.b<<' '<<(int)tmp.c<<endl;
				h[tar&511][j]=min(h[tar&511][j],tmp);
			}
		}
	}
/*	fd1(i,len){
		fz1(j,n){
			if(h[i][j].a){
				cerr<<i<<' '<<j<<' '<<(int)h[i][j].a<<' '<<(int)h[i][j].b<<' '<<(int)h[i][j].c<<endl;
			} 
		}
	}*/
	fd1(i,len){
		fz1(j,m)if(h[i&511][px[j]].c){
			h[i-1&511][py[j]]=min(h[i-1&511][py[j]],add(h[i&511][px[j]],pz[j]));
		}
		memset(h[i&511],0,sizeof(h[0]));
	}
/*	i=0;
		fz1(j,n){
			if(h[i][j].a){
				cerr<<i<<' '<<j<<' '<<(int)h[i][j].a<<' '<<(int)h[i][j].b<<' '<<(int)h[i][j].c<<endl;
			} 
		}*/
	fz1(i,n){
		if(h[0][i].c) printf("%d",(int)(((h[0][i].a%mod*ek)%mod+h[0][i].b%mod+mod)%mod*qp(h[0][i].c%mod,mod-2)%mod));
		else printf("-1");
		printf(" ",spln(i,n));
	}
	puts("");
}
int main()
{
//	freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	int t;cin>>_>>t;
	while(t--){
//		flg=(t==6185-4220);
		solve(); 
	}
	return 0;
}