#include<iostream>
#include<cstdio>
#include<vector>
#define M 40000
#define N 400
#define mod 998244353
using namespace std;
const int inv2=(mod+1)>>1;
const __int128 inf=(__int128)(1e30);
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 MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
struct reads
{
	int num;
	long long data;
};
int S,T,n,m,maxn,k,res;
__int128 dp[M+1][N+1];
vector<reads>E[N+1];
void add(int x,int y,long long z)
{
	E[x].push_back((reads){y,z});
	return;
}
int main()
{
	string s;
	int x,y;
	long long z;
	bool op;
	S=read(),T=read();
	while (T--)
	{
		n=read(),m=read(),cin>>s,k=op=res=0,maxn=n*m;
		for (int i=1;i<=n;++i) E[i].clear();
		for (int i=1;i<=m;++i) x=read(),y=read(),z=read(),add(x,y,z);
		for (int i=0;i<s.length();++i)
		{
			if (!op)
			{
				k=k*10+s[i]-'0';
				if (k>maxn) op=1;
			}
			res=(10ll*res+s[i]-'0')%mod;
		}
		for (int i=0;i<=maxn+2;++i)
			for (int j=1;j<=n;++j)
				dp[i][j]=inf;
		dp[0][1]=0;
		for (int i=1;i<=maxn+2;++i)
			for (int j=1;j<=n;++j)
				for (int t=0;t<E[j].size();++t)
					dp[i][E[j][t].num]=min(dp[i][E[j][t].num],dp[i-1][j]+E[j][t].data);
	    if (!op)
		{
			for (int i=1;i<=n;++i)
			{
				if (dp[k][i]==inf) printf("-1 ");
				else printf("%d ",(int)(dp[k][i]%mod));
			}
		}
		else
		{
			if (((s[(int)(s.length())-1]-'0')&1)==(maxn&1))
			{
				for (int i=1;i<=n;++i)
				{
					if (dp[maxn][i]==inf) printf("-1 ");
					else printf("%d ",(int)(MD(dp[maxn][i]%mod+1ll*((dp[maxn+2][i]-dp[maxn][i])%mod)*MD2(res-maxn)%mod*inv2%mod)));
				}
			}
			else
			{
				for (int i=1;i<=n;++i)
				{
					if (dp[maxn-1][i]==inf) printf("-1 ");
					else printf("%d ",(int)(MD(dp[maxn-1][i]%mod+1ll*((dp[maxn+1][i]-dp[maxn-1][i])%mod)*MD2(res-(maxn-1))%mod*inv2%mod)));
				}
			}
		}
		puts("");
	}
	return 0;
}