#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int myinf=100000001;
int cnt;
int next[1000010];
int en[1000010];
int num[1000010];
int fir[1000010];
int dis[1000010];
int team[10000010];
int b[1000010];
int ans[1000010];
int minl;
int t;
int n,m,k,p; 
int x,y,z;
int left1,right1;
void add(int u,int v,int len)
{
	cnt++;
	next[cnt]=fir[u];
	fir[u]=cnt;
	en[cnt]=v;
	num[cnt]=len;
}
int main()
{
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		cnt=0;
		scanf("%d %d %d %d",&n,&m,&k,&p);
		for(int j=1;j<=m;j++)
		{
			scanf("%d %d %d",&x,&y,&z);
			add(x,y,z);
		}
		for(int j=1;j<=n;j++)
			dis[j]=myinf;
		for(int j=1;j<=n;j++)
			b[j]=0;
		ans[1]=1;
		left1=1;
		right1=1;
		dis[1]=0;
		b[1]=1;
		team[1]=1;
		while(left1<=right1)
		{
			int u=team[left1];
			for(int kk=fir[u];kk;kk=next[kk])
			{
				if(dis[en[kk]]>dis[u]+num[kk])
				{
					dis[en[kk]]=dis[u]+num[kk];
					ans[en[kk]]=ans[u];
					if(b[en[kk]]==0)
					{
						right1++;
						team[right1]=en[kk];
						b[en[kk]]=1;
					}
				}
				else 
				if(dis[en[kk]]==dis[u]+num[kk])
				{
					ans[en[kk]]=ans[en[kk]]+ans[u];
					ans[en[kk]]=ans[en[kk]]%p;
				}
			}
			left1++;
			b[u]=0;
		}
		for(int j=1;j<=n;j++)
			printf("%d ",ans[j]);//输出答案 
		printf("\n");
		cnt=0;
		for(int j=1;j<=m;j++)
			{
				fir[j]=0;
				en[j]=0;
				next[j]=0;
				num[j]=0;//清零 
			}
	}
	return 0; 
}