#include<bits/stdc++.h>
#define ll long long
#define GC getchar()
#define N 1000100
#define M 9999999999999999
#define PC putchar
using namespace std;
ll re(){
	ll s=0,b=1; char c=GC;
	while(c>'9'||c<'0'){if(c=='-')b=-b; c=GC;}
	while(c<='9'&&c>='0'){s=(s<<1)+(s<<3)+(c^48); c=GC;}
	return s*b;
}
void ks(ll s){
	if(s>=10)ks(s/10); PC((s%10)|48);
}
int n,m,S,x,y,fl,he[N],tt,dl[N],t,lt[N];
ll K,di[N][2],z;
bool vi[N][2];
struct A{int ne,to; ll z; bool fl;}b[N];
struct B{int x,o; ll z;};
struct cmB{bool operator()(B x,B y){return x.z>y.z;}};
priority_queue<B,vector<B>,cmB> q;
void wo(){
	for(int i=1; i<=n; ++i)he[i]=vi[i][0]=vi[i][1]=lt[i]=0;
	tt=t=0;
	n=re(),m=re(); S=re(); K=re();
	for(int i=1; i<=n; ++i)di[i][0]=di[i][1]=M; 
	for(int i=1; i<=m; ++i){
		x=re(); y=re(); z=re(); fl=re();
		b[++tt].to=y; b[tt].ne=he[x]; he[x]=tt;
		b[tt].z=z; b[tt].fl=fl;
	}
	B o; o.x=S; o.z=0; o.o=0; di[S][0]=0; q.push(o);
	fl=0;
	while(!q.empty()){
		o=q.top(); q.pop();
		if(vi[o.x][o.o])continue; vi[o.x][o.o]=1;
		if(!o.o){
			for(int i=he[o.x]; i; i=b[i].ne){
				int v=b[i].to,nfl=b[i].fl; ll z=o.z+b[i].z;
				if(di[v][nfl]>z){
					di[v][nfl]=z;
					B ne; ne.x=v; ne.o=nfl; ne.z=z; q.push(ne);
				}
			}
		} else{
			for(int i=he[o.x]; i; i=b[i].ne){
				int v=b[i].to,nfl=b[i].fl;  ll z=o.z+b[i].z-K;
				lt[v]=o.x;
				if(di[v][nfl]>z){
					di[v][nfl]=z;
					B ne; ne.x=v; ne.o=nfl; ne.z=z; q.push(ne);
				}
			}
			if(!fl){
				fl=1;
				for(int i=1; i<=n; ++i){
					if(!lt[i]){
						if(di[i][0]>o.z){
							di[i][0]=o.z;
							B ne; ne.x=i; ne.o=0; ne.z=o.z; q.push(ne);
						}
					} else{
						if(!vi[i][0])dl[++t]=i;
					}
				}
			} else{
				for(int i=1; i<=t; ++i){
					if(lt[dl[i]]!=o.x){
						int v=dl[i];
						if(di[v][0]>o.z){
							di[v][0]=o.z;
							B ne; ne.x=v; ne.o=0; ne.z=o.z; q.push(ne); 
						}
						swap(dl[i],dl[t]); i--; t--;
					}
				}
			}
		}
	}
	for(int i=1; i<=n; ++i){
		ll an=min(di[i][0],di[i][1]);
		if(an==M)PC('-'),PC('1');
		 else ks(an); 
		PC(' ');
	} PC('\n');
}
int main(){
	int T=re();
	while(T--)wo();
}