#include<bits/stdc++.h>
#define int __int128
#define modddd 998244353
using namespace std;
long long n,m,Eu[605],Ev[605];
long long k,Ew[605];
__int128 inf;
inline __int128 ksm(__int128 a,__int128 b){
	if(b==0){
		return 1;
	}
	if(b==1){
		return a;
	}
	__int128 tmp=ksm(a,b/2);
	if(b%2==0){
		return tmp*tmp%modddd;
	}
	else{
		return tmp*tmp%modddd*a%modddd;
	}
}
inline __int128 inv(__int128 x){
	return ksm(x,modddd-2)%modddd;
}
inline void write(__int128 &a){
	if(a<0){
		putchar('-');
		a=-a;
	}
	if(a>=10){
		__int128 ovo=a/10;
		write(ovo);
	}
	putchar(a%10+'0');
}
namespace Solve1{
	__int128 dis[605],updis[605];
	inline void wrk(){
		fill(updis+1,updis+n+1,2*inf);
		for(int i=1;i<=m;i++){
			updis[Ev[i]]=min(updis[Ev[i]],dis[Eu[i]]+Ew[i]);
		}
		copy_n(updis+1,n,dis+1);
	}
	__int128 cyc[605][605], ray[605][605];
	inline void SLVR() {
		fill(dis+1,dis+n+1,2*inf);
		dis[1]=0;
		long long LEN=n*(n+1)*3;
		if(k<=2*LEN){
			for(int t=1;t<=k;t++){
				wrk();
			}
		}
		else{
			long long mid=k-LEN*2;
			for(int i=1;i<=n;i++){
				fill(dis+1,dis+n+1,2*inf);
				dis[i]=0;
				for(int j=1;j<=n;j++){
					wrk();
					if(dis[i]<inf){
						cyc[i][j]=dis[i];
					}
					else{
						cyc[i][j]=-1;
					}
				}
			}
			fill(dis+1,dis+n+1,2*inf);
			dis[1]=0;
			for(int t=1;t<=LEN;t++){
				wrk();
			}
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					ray[i][j]=2*inf;
				}
			}
			for(int i=1;i<=n;i++){
				if(dis[i]<inf){
					for(int j=1;j<=n;j++){
						if(~cyc[i][j]){
							long long t=mid/j+1;
							long long sm=t*j-mid;
							ray[sm][i]=min(ray[sm][i],dis[i]+(__int128)t*cyc[i][j]);
						}
					}
				}
			}
			fill(dis+1,dis+n+1,2*inf);
			for(int t=1;t<=LEN;t++){
				wrk();
				if(t<=n){
					for(int i=1;i<=n;i++){
						dis[i]=min(dis[i],ray[t][i]);
					}
				}
			}
		}
		for(int i=1;i<=n;i++){
			if(dis[i]>inf){
				cout<<-1;
			}
			else{
				__int128 anssss=dis[i]%modddd;
				write(anssss);
			}
			if(i==n){
				cout<<endl;
			}
			else{
				cout<<" ";
			}
		}
	}
}
namespace Solve2{
	__int128 dis[605],updis[605];
	struct Frac{
		int L;
		__int128 S;
		Frac(__int128 sum=0,int len=0){
			L=len;
			S=sum;
		}
	};
	inline bool operator<(const Frac &lhs,const Frac &rhs){
		return lhs.S*rhs.L<rhs.S*lhs.L;
	}
	inline bool operator==(const Frac &lhs,const Frac &rhs){
		return lhs.S*rhs.L==rhs.S*lhs.L;
	}
	struct Node{
		Frac a,b;
		Node(Frac A=Frac(1,1),Frac B=Frac(1,1)){
			a=A;
			b=B;
		}
	};
	bool flag;
	__int128 K,LIM;
	inline bool operator<(const Node &x,const Node &y){
		__int128 vl1=x.a.S*y.a.L;
		__int128 vl2=x.a.L*y.a.S;
		if(vl1==vl2){
			return x.b<y.b;
		}
		if(flag){
			return vl1<vl2;
		}
		__int128 dt=vl1-vl2;
		return (-LIM<=dt&&dt<=LIM)?dt*K+x.b.S*y.b.L<x.b.L*y.b.S:vl1<vl2;
	}
	Node Nd_inf=Node(Frac((__int128)1e31,1),Frac((__int128)1e31,1));
	inline void wrk(){
		fill(updis+1,updis+1+n,2*inf);
		for(int i=1;i<=m;i++){
			updis[Ev[i]]=min(updis[Ev[i]],dis[Eu[i]]+Ew[i]);
		}
		copy_n(updis+1,n,dis+1);
	}
	Node tempdis[605],tempud[605];
	inline void SAP(){
		fill(tempud+1,tempud+1+n,Nd_inf);
		for(int i=1;i<=m;i++){
			auto cur=tempdis[Eu[i]];
			cur.b.S+=(__int128)Ew[i]*cur.b.L;
			tempud[Ev[i]]=min(tempud[Ev[i]],cur);
		}
		copy_n(tempud+1,n,tempdis+1);
	}
	__int128 cyc[605][605];
	Node ray[605][605];
	inline void SLVR(string S) {
		fill(dis+1,dis+n+1,2*inf);
		dis[1]=0;
		long long LEN=n*(n+1)*2;
		long double tmp=0;
		for(auto ch:S){
			tmp=tmp*10+(ch^48);
		}
		if(tmp>(__int128)1e27){
			flag=1;
		}
		else{
			flag=0;
			K=0;
			for(auto ch:S){
				K=K*10+(ch^48);
			}
			K -= LEN * 2;
			if(K){
				LIM=2e36/K;
			}
		}
		for(int i=1;i<=n;i++){
			fill(dis+1,dis+n+1,2*inf);
			dis[i]=0;
			for(int j=1;j<=n;j++){
				wrk();
				if(dis[i]<inf){
					cyc[i][j]=dis[i];
				}
				else{
					cyc[i][j]=-1;
				}
			}
		}
		fill(dis+1,dis+n+1,2*inf);
		dis[1]=0;
		for(int t=1;t<=LEN;t++){
			wrk();
		}
		vector<int>pos(n+1);
		__int128 w=0;
		for(int i=1;i<=n;i++){
			w=0;
			for(auto &ch:S){
				w=w*10+(ch^48);
				w%=i;
			}
			pos[i]=((w-LEN*2)%i+i)%i;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				ray[i][j]=Nd_inf;
			}
		}
		for(int i=1;i<=n;i++){
			if(dis[i]<inf){
				__int128 sm=0;
				for(int j=1;j<=n;j++){
					if(~cyc[i][j]){
						sm=j-pos[j];
						ray[sm][i]=min(ray[sm][i],Node(Frac(cyc[i][j],j),Frac(dis[i]*j+sm*cyc[i][j],j)));
					}
				}
			}
		}
		for(int i=1;i<=n;i++){
			tempdis[i]=Nd_inf;
		}
		for(int t=1;t<=LEN;t++){
			SAP();
			if(t<=n){
				for(int i=1;i<=n;i++){
					tempdis[i]=min(tempdis[i],ray[t][i]);
				}
			}
		}
		__int128 num=0;
		for(auto ch:S){
			num*=10;
			num%=modddd;
			num+=(ch^48);
			num%=modddd;
		}
		num=(num%modddd+modddd)%modddd;
		num-=(LEN%modddd*2%modddd);
		num=(num%modddd+modddd)%modddd;
		for(int i=1;i<=n;i++){
			auto r=tempdis[i];
			if((long double)r.a.S/r.a.L>(__int128)2e18){
				cout<<-1<<" ";
			}
			else{
				__int128 awawa=((num*r.a.S%modddd+r.b.S%modddd)%modddd)%modddd*inv(r.b.L%modddd)%modddd;
				awawa%=modddd;
				write(awawa);
				putchar(' ');
			}
		}
		cout<<endl;
	}
}
inline void solve(){
	string S;
	cin>>n>>m>>S;
	long double tmp=0;
	for(auto ch:S){
		tmp=tmp*10+(ch^48);
	}
	for(int i=1;i<=m;i++){
		cin>>Eu[i]>>Ev[i]>>Ew[i];
	}
	if(tmp<=n*n*10){
		k=0;
		for(auto ch:S){
			k=k*10+(ch^48);
		}
		Solve1::SLVR();
		return;
	}
	Solve2::SLVR(S);
}
long long test_case;
signed main(){
	inf=numeric_limits<__int128>::max()/10;
	cin>>test_case>>test_case;
	while(test_case--){
		solve();
	}
	return 0;
}

同一份代码，交到 C++14(O2) 就可以 AC 而 C++14(GCC9) (O2) 却不行，为什么呢/xk