#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 600
#define mod 998244353
using namespace std;
const long long infs=(long long)(2e18);
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;
}
struct reads
{
	int num;
	long long data;
};
int S,T,n,m,tk,p[N+1];
long long delta[N+1],minn[N+1],sminn[N+1];
bool used[N+1];
__int128 sk,ans[N+1],dp[N+1][N+1][2];
string k;
vector<reads>E[N+1];
void add(int x,int y,long long z)
{
	E[x].push_back((reads){y,z}),E[y].push_back((reads){x,z});
	return;
}
bool cmp(int x,int y)
{
	return minn[x]<minn[y];
}
int main()
{
	int x,y,rst;
	long long z;
	S=read(),T=read();
	for (int qt=1;qt<=T;++qt)
	{
		n=read(),m=read(),sk=tk=0,cin>>k,rst=k[(int)(k.length())-1];
		for (int i=1;i<=n;++i) E[i].clear(),minn[i]=infs;
		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(),minn[x]=min(minn[x],z),E[x].push_back((reads){y,z});
		if (sk!=inf)
		{
			for (int i=1;i<=n;++i) ans[i]=INF;
			for (int i=1;i<=n;++i)
				if (minn[i]!=infs)
				{
					for (int j=0;j<=m;++j)
						for (int k=1;k<=n;++k)
							for (int op=0;op<=1;++op)
								dp[j][k][op]=INF;
					dp[0][1][i==1]=0;
					for (int j=1;j<=m;++j)
						for (int k=1;k<=n;++k)
							for (int t=0;t<E[k].size();++t)
								for (int op=0;op<=1;++op)
									dp[j][E[k][t].num][op|(E[k][t].num==i)]=min(dp[j][E[k][t].num][op|(E[k][t].num==i)],dp[j-1][k][op]+E[k][t].data);
					for (int j=0;j<=m;++j)
						if (sk>=j&&!((sk-j)&1))
						{
							for (int k=1;k<=n;++k) ans[k]=min(ans[k],dp[j][k][1]+(sk-j)*minn[i]);
						}
				}
			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) ans[i]=INF,sminn[i]=infs,p[i]=i;
			sort(p+1,p+n+1,cmp);
			for (int i=1;i<=n;++i)
				if (minn[p[i]]!=infs)
				{
					for (int j=0;j<=m;++j)
						for (int k=1;k<=n;++k)
							for (int op=0;op<=1;++op)
								dp[j][k][op]=INF;
					dp[0][1][p[i]==1]=0;
					for (int j=1;j<=m;++j)
						for (int k=1;k<=n;++k)
							for (int t=0;t<E[k].size();++t)
								for (int op=0;op<=1;++op)
									dp[j][E[k][t].num][op|(E[k][t].num==p[i])]=min(dp[j][E[k][t].num][op|(E[k][t].num==p[i])],dp[j-1][k][op]+E[k][t].data);
					for (int j=0;j<=m;++j)
						if ((rst&1)==(j&1))
						{
							for (int k=1;k<=n;++k)
								if (dp[j][k][1]!=INF)
								{
									if (sminn[k]==infs) sminn[k]=minn[p[i]],ans[k]=dp[j][k][1]-(__int128)(j)*minn[p[i]];
									else if (sminn[k]==minn[p[i]]) ans[k]=min(ans[k],dp[j][k][1]-(__int128)(j)*minn[p[i]]);
								}
						}
				}
			for (int i=1;i<=n;++i)
			{
				if (ans[i]==INF) printf("-1 ");
				else printf("%d ",MD2((ans[i]+(__int128)(tk)*sminn[i])%mod));
			}
			puts("");
		}
	}
	return 0;
}