#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;
const ll inf=1e17;
ll ans[N];
ll n,m,s,k;
//建立边
struct node{
	ll v,w,s;
};
vector<node>g[N];//边权值 

struct node2{
	ll x,w,s;
	bool operator<(const node2& a)const {
		return w>a.w;//希望小的在前就放大的 
	}
};

ll dis[N][2];
int vis[N][2]; 
void dij(int st){
	priority_queue<node2>q;
	q.push((node2){st,0,0});
	set<int>s;
	for(int i=1;i<=n;i++)
	{
		s.insert(i);
	}
	dis[st][0]=0;
	while(!q.empty()){
		auto a=q.top();//node2
		q.pop();
		//进行更新
		int u=a.x,val=a.w,flag=a.s;
		if(vis[u][flag])	continue;
		vis[u][flag]=1;
		if(!flag){
			//0的情况 
			s.erase(u);
		}
		else {
			vector<int>temp;
			for(int i=0;i<g[u].size();i++){
				auto b=g[u][i];//获得第二个点
				ll v=b.v,d=b.w,ss=b.s;
				s.erase(v);//这种情况下也是可以进行删除的,后面的情况下是不会在进入的 
				temp.push_back(v);
			}//边是node1 	
			for(auto v:s){
				if(dis[v][0]>val){
					dis[v][0]=val;
					q.push((node2){v,val,0});
				}
			}//重新加入
			//如果是1来的话 
			s.clear();
			s.insert(temp.begin(),temp.end());
		}

		int y=0;
		if(flag)	y-=k;
		for(int i=0;i<g[u].size();i++){
			auto b=g[u][i];//获得第二个点
			ll v=b.v,d=b.w,s=b.s;
			if(dis[v][s]>val+d+y){
				dis[v][s]=val+d+y;
				q.push((node2){v,dis[v][s],s});
			}
			//不特殊直接写	
		}//边是node1,直接进行跑最短路	,直接按照之前的更新 		
	} 
}//第一个是原点 
int main(){
	int t;
	scanf("%d",&t);
	while(t--){

		scanf("%d%d%d%d",&n,&m,&s,&k);
		for(int i=1;i<=n;i++){
			g[i].clear();
			dis[i][0]=dis[i][1]=inf;//到不了是-1 
			vis[i][0]=vis[i][1]=0;
		}		
		int x,y,w,t;
		for(int i=1;i<=m;i++){
			scanf("%d%d%d%d",&x,&y,&w,&t);
			g[x].push_back((node){y,w,t});
		}
		dij(s);
		for(int i=1;i<=n;i++){
			ans[i]=min(dis[i][0],dis[i][1]); 
		}
		for(int i=1;i<=n;i++){
			printf("%lld ",(ans[i]==inf)?(-1):ans[i]);
		}
		puts("");
	}
	return 0;
}