#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=300+5,M=8e5+5,K=(1<<25)+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const int INF=1e9+7;mt19937 rnd(time(0));
using LL=__int128;
void read(LL &x){
	char c=Gc();x=0;
	while(c<'0'||c>'9') c=Gc();
	while(c>='0'&&c<='9') x=x*10+c-48,c=Gc();
}
int n,m,X[N*2],Y[N*2];ll Z[N*2];
LL f[N*N*2][N],k,g[N][N][N],dp[N*N][N];
void Solve(){
	int i,j,h;scanf("%d%d",&n,&m);read(k);
	for(i=1;i<=m;i++) scanf("%d%d%lld",&X[i],&Y[i],&Z[i]);
	for(i=0;i<=2*n*n;i++) fill(f[i]+1,f[i]+n+1,(LL)1e36);
	f[0][1]=0;for(i=1;i<=2*n*n;i++){
		for(j=1;j<=m;j++) f[i][Y[j]]=min(f[i][Y[j]],f[i-1][X[j]]+Z[j]);
	}
	if(k<=2*n*n){
		for(i=1;i<=n;i++) printf("%d%c",f[k][i]>=1e36?-1:(int)(f[k][i]%mod)," \n"[i==n]);
		return;
	}
	for(i=0;i<=n;i++) for(j=1;j<=n;j++) fill(g[i][j]+1,g[i][j]+n+1,(LL)1e36);
	for(i=1;i<=n;i++) g[0][i][i]=0;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			for(h=1;h<=m;h++) g[i][j][Y[h]]=min(g[i][j][Y[h]],g[i-1][j][X[h]]+Z[h]);
		}
	}
	for(i=0;i<=n*(n+1);i++) fill(dp[i]+1,dp[i]+n+1,(LL)1e38); 
	for(i=1;i<=n;i++){
		pair<LL,int> cir=make_pair((LL)1e30,1);
		for(j=1;j<=n;j++) if(g[j][i][i]<1e30&&g[j][i][i]*1.0/j<cir.fi*1.0/cir.se) cir=make_pair(g[j][i][i],j);
		if(cir.fi>1e29) continue;
		// cerr<<i<<' '<<(ll)cir.fi<<' '<<cir.se<<'\n';
		for(j=n*n-n;j<=n*n;j++){
			int kk=(k-j-n*n)%cir.se;//cerr<<kk<<'\n';
			dp[n*n+kk][i]=min(dp[n*n+kk][i],(k-j-n*n-kk)/cir.se*cir.fi+f[j][i]);
		}
	}
	for(i=n*(n+1);i;i--){
		for(j=1;j<=m;j++) dp[i-1][Y[j]]=min(dp[i-1][Y[j]],dp[i][X[j]]+Z[j]);
	}
	for(i=1;i<=n;i++) printf("%d%c",dp[0][i]>1e36?-1:(int)(dp[0][i]%mod)," \n"[i==n]);
}
int main(){
	int id,t=1;
	scanf("%d%d",&id,&t);
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}