#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define M 180000
#define N 300
#define mod 998244353
using namespace std;
const __int128 INF=(__int128)(1e36);
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
struct reads
{
	int num;
	long long data;
};
int S,T,n,m,tk,inv[N+1],md[N+1],num[M+1][N+1];
__int128 dsp[N+1][N+1],DP[N+1][N+1],DSP[N+1][N+1],sk;
string k;
vector<reads>E[N+1];
struct frac
{
	__int128 x;
	int y;
	bool operator < (const frac &t)const
	{
		return x*t.y<y*t.x;
	}
	bool operator >= (const frac &t)const
	{
		return x*t.y>=y*t.x;
	}
	bool operator == (const frac &t)const
	{
		return x*t.y==y*t.x;
	}
	bool operator != (const frac &t)const
	{
		return x*t.y!=y*t.x;
	}
};
frac operator + (frac a,frac b)
{
	return (frac){a.x*b.y+a.y*b.x,a.y*b.y};
}
frac operator - (frac a,frac b)
{
	return (frac){a.x*b.y-a.y*b.x,a.y*b.y};
}
struct rds
{
	frac a,b;
	bool operator < (const rds &t)const
	{
		return a!=t.a?a<t.a:b<t.b;
	}
	bool operator == (const rds &t)const
	{
		return a==t.a&&b==t.b;
	}
	bool operator != (const rds &t)const
	{
		return a!=t.a||b!=t.b;
	}
};
rds zero=(rds){(frac){0,1},(frac){0,1}},inf=(rds){(frac){1,0},(frac){1,0}},dp[2][N+1],delta[N+1][N+1];
rds operator + (rds x,rds y)
{
	if (x==inf||y==inf) return inf;
	x.a=x.a+y.a,x.b=x.b+y.b;
	if (x.b>=(frac){sk,1}) x.a=x.a+(frac){1,1},x.b=x.b-(frac){sk,1};
	return x;
}
rds operator - (rds x,rds y)
{
	if (x==inf) return inf;
	x.a=x.a-y.a,x.b=x.b-y.b;
	if (x.b<(frac){0,1}) x.a=x.a-(frac){1,1},x.b=x.b+(frac){sk,1};
	return x;
}
rds change(rds x)
{
	__int128 d;
	if (x.b.x>=0) d=x.b.x/x.b.y/sk,x.a=x.a+(frac){d,1},x.b=x.b-(frac){d*sk,1};
	else d=(-x.b.x+x.b.y*sk-1)/x.b.y/sk,x.a=x.a-(frac){d,1},x.b=x.b+(frac){d*sk,1};
	return x;
}
int get(rds x)
{
	if (x==inf) return -1;
	__int128 res=(x.a.x%mod)*inv[x.a.y]*tk+(x.b.x%mod)*inv[x.b.y];
	res=MD2(res%mod);
	return res;
}
int main()
{
	int x,y,d,op;
	long long z;
	inv[1]=1;
	for (int i=2;i<=N;++i) inv[i]=MD2(-1ll*(mod/i)*inv[mod%i]%mod);
	S=read(),T=read();
	for (int qt=1;qt<=T;++qt)
	{
		n=read(),m=read(),sk=tk=0,cin>>k;
		for (int i=2;i<=n;++i) md[i]=0;
		for (int i=1;i<=n;++i) E[i].clear();
		for (int i=0;i<k.length();++i)
		{
			sk=min(sk*10+k[i]-'0',INF),tk=(tk*10ll+k[i]-'0')%mod;
			for (int j=2;j<=n;++j) md[j]=(md[j]*10ll+k[i]-'0')%j;
		}
		for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),E[x].push_back((reads){y,z});
		for (int i=1;i<=n;++i)
		{
			for (int j=0;j<=n;++j)
				for (int k=1;k<=n;++k)
					DSP[j][k]=INF;
			DSP[0][i]=0;
			for (int j=1;j<=n;++j)
				for (int k=1;k<=n;++k)
					for (int t=0;t<E[k].size();++t)
						DSP[j][E[k][t].num]=min(DSP[j][E[k][t].num],DSP[j-1][k]+E[k][t].data);
			for (int j=0;j<=n;++j) DP[j][i]=DSP[j][i];
		}
		for (int i=1;i<=n;++i)
			for (int j=n*n-i+1;j<=n*n;++j)
				num[i][j%i]=j;
		if (sk<=10*n*n)
		{
			for (int i=1;i<=n;++i) dsp[0][i]=INF;
			dsp[0][1]=0,op=0;
			for (int i=1;i<=sk;++i)
			{
				op^=1;
				for (int j=1;j<=n;++j) dsp[op][j]=INF;
				for (int j=1;j<=n;++j)
					for (int k=0;k<E[j].size();++k)
						dsp[op][E[j][k].num]=min(dsp[op][E[j][k].num],dsp[op^1][j]+E[j][k].data);
			}
			for (int i=1;i<=n;++i) printf("%d ",dsp[op][i]==INF?-1:dsp[op][i]%mod);
			puts("");
		}
		else
		{
			for (int i=0;i<n;++i)
				for (int j=1;j<=n;++j)
					delta[i][j]=inf;
			op=0;
			for (int i=1;i<=n;++i) dsp[0][i]=INF;
			dsp[0][1]=0;
			for (int i=1;i<=n*n;++i)
			{
				op^=1;
				for (int j=1;j<=n;++j) dsp[op][j]=INF;
				for (int j=1;j<=n;++j)
					for (int k=0;k<E[j].size();++k)
						dsp[op][E[j][k].num]=min(dsp[op][E[j][k].num],dsp[op^1][j]+E[j][k].data);
				if (i>=n*n-n+1)
				{
					for (int j=1;j<=n;++j)
						if (dsp[op][j]!=INF)
						{
							for (int k=1;k<=n;++k)
								if (DP[k][j]!=INF)
									d=num[k][((md[k]-i)%k+k)%k],delta[n*n-d][j]=min(delta[n*n-d][j],change((rds){(frac){DP[k][j],k},(frac){dsp[op][j],1}+(frac){-DP[k][j]*(d+i),k}}));
						}
				}
			}
			op=0;
			for (int i=1;i<=n;++i) dp[0][i]=delta[0][i];
			for (int i=n*n-1;i>=0;--i)
			{
				op^=1;
				for (int j=1;j<=n;++j) dp[op][j]=inf;
				if (i>=n*n-n+1)
				{
					for (int j=1;j<=n;++j) dp[op][j]=delta[n*n-i][j];
				}
				for (int j=1;j<=n;++j)
					for (int k=0;k<E[j].size();++k)
						dp[op][E[j][k].num]=min(dp[op][E[j][k].num],dp[op^1][j]+change((rds){(frac){0,1},(frac){E[j][k].data,1}}));
			}
			for (int i=1;i<=n;++i) printf("%d ",get(dp[op][i]));
			puts("");
		}
	}
	return 0;
}