#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
struct node
{
	int v; ll w; int ty;
	bool operator < (const node& rhs) const
	{
		return w > rhs.w;
	}
};
vector<node> g[N];
int vis[N], id, n, m, s, k;
ll d[N][2];

void solve()
{
	set<int> S;
	priority_queue<node> q;
	_for(i, 1, n) d[i][0] = d[i][1] = 1e18, S.insert(i);
	d[s][0] = id = 0;
	q.push({s, 0, 0});

	while(!q.empty())
	{
		auto [u, w, ty] = q.top(); q.pop();
		S.erase(u);

		if(ty)   //如果上一次走了特殊边
		{
			id++;
			for(auto [v, w2, ty2]: g[u]) vis[v] = id;
			vector<int> del;
			for(int x: S)
				if(vis[x] != id)
				{
					del.push_back(x);
					d[x][0] = d[u][ty];
					q.push({x, d[x][0], 0});
				}
			for(int x: del) S.erase(x);
		}
		
		int t = ty ? -k : 0;
		for(auto [v, w2, ty2]: g[u]) 
			if(d[u][ty] + w2 + t < d[v][ty2])
			{
				d[v][ty2] = d[u][ty] + w2 + t;
				q.push({v, d[v][ty2], ty2});
			}
	}
}

int main()
{
	int T; scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d%d%d", &n, &m, &s, &k);
		_for(i, 1, n) vis[i] = 0, g[i].clear();
		while(m--)
		{
			int u, v, w, ty;
			scanf("%d%d%d%d", &u, &v, &w, &ty);
			g[u].push_back({v, w, ty});
		}

		solve();

		_for(i, 1, n) 
		{
			ll cur = min(d[i][0], d[i][1]);
			printf("%lld ", cur == 1e18 ? -1 : cur);
		}
		puts("");
	}

	return 0;
}