#include<iostream>
#include<cstdio>
#define N 300
#define mod 998244353
using namespace std;
const __int128 inf=(__int128)(1e19);
const __int128 INF=(__int128)(1e37);
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;
}
int S,T,n,m,tk;
long long delta[N+1],minn[N+1];
__int128 sk,ans[N+1],s[N+1],sminn;
string k;
int main()
{
	int x,y;
	long long z;
	__int128 res;
	S=read(),T=read();
	while (T--)
	{
		n=read(),m=read(),sk=tk=0,cin>>k;
		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 i=1;i<=m;++i) x=read(),y=read(),z=read(),delta[max(x,y)]=z;
		for (int i=2;i<=n;++i) s[i]=s[i-1]+delta[i];
		for (int i=2;i<=n;++i) minn[i]=i==2?delta[i]:min(minn[i-1],delta[i]);
		if (sk!=inf)
		{
			for (int i=1;i<=n;++i) ans[i]=INF;
			for (int i=2;i<=n;++i)
				for (int j=1;j<=i;++j)
					if (sk>=(i<<1)+j&&!((sk-(i<<1)+j+1)&1))
						ans[j]=min(ans[j],(sk-(i<<1)+j+1)*minn[i]+(s[i]<<1)-s[j]);
			for (int i=1;i<=n;++i) printf("%d ",ans[i]==INF?-1:ans[i]%mod);
			puts("");
		}
		else
		{
			for (int i=1;i<=n;++i)
			{
				if (((i-1)&1)==(k[(int)(k.length())-1]&1)) res=(__int128)(tk-(n<<1)+i+1)*minn[n]+(s[n]<<1)-s[i],printf("%d ",MD2(res%mod));
				else printf("-1 ");
			}
			puts("");
		}
	}
	return 0;
}