//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define lson 2*p
#define rson 2*p+1
#define x first
#define y second
#define lowbit(x) x&-x
//#define endl "\n"
const int N=1e6+10;
const int mod=998244353;
struct node {
	int x,w,op;
};
vector<node> g[N];
struct node1 {
	int x,d,st;
	bool operator < (const node1 &t) const {
		return d>t.d;
	}
};
int dist[N][2],vis[N][2];
void solve() {
	int n,m,s,k;
	cin>>n>>m>>s>>k;
	for(int i=1;i<=n;i++) g[i].clear();
	for(int i=1;i<=m;i++) {
		int u,v,w,op;
		cin>>u>>v>>w>>op;
		g[u].push_back({v,w,op});
	}
	priority_queue<node1> q;
	for(int i=0;i<=n;i++) {
		dist[i][0]=dist[i][1]=1e18;
		vis[i][0]=vis[i][1]=0;
	}
	dist[s][0]=0;
	q.push({s,0,0});
	set<int> S;
	for(int i=1;i<=n;i++) if(i!=s) S.insert(i);
	
	while(q.size()) {
		auto p=q.top();
		q.pop();
		int x=p.x;
		int st=p.st;
		if(!st) S.erase(x);
		else {
			set<int> S1=S;
			for(auto it:g[x]) {
				int y=it.x;
				S1.erase(y);
			}
			for(int y:S1) {
				dist[y][0]=dist[x][1];
				q.push({y,dist[y][0],0});
				S.erase(y);
			}
		} 
		if(vis[x][st]) continue;
		vis[x][st]=1;
		for(auto it:g[x]) {
			int y=it.x,op=it.op,w=it.w;
			if(dist[y][op]>dist[x][st]+w-k*(st==1)) {
				dist[y][op]=dist[x][st]+w-k*(st==1);
				q.push({y,dist[y][op],op});
			}
		}
	}
	for(int i=1;i<=n;i++) {
		if(min(dist[i][0],dist[i][1])==1e18) cout<<-1<<" ";
		else cout<<min(dist[i][0],dist[i][1])<<" ";
	}
	cout<<endl;
} 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	cin>>T;
	while(T--) {
		solve();
	}
}