#include <bits/stdc++.h>
#pragma GCC optimize("trapv")
using namespace std;

const int N = 1e6+5;

struct edge
{
	int id;
	long long len;
	bool flag;

	bool operator<(const edge &x) const
	{
		if(x.len != len)
			return len > x.len;
		return id > x.id;
	}
};

vector<edge> a[N];
long long dis[N][2];
int bel[N];
priority_queue<edge> pq;
set<int> s;

void dijk(int start, long long K)
{
	pq.push({start, 0, 0});
	dis[start][0] = 0;

	int cnt = 0;
	while(!pq.empty())
	{
		edge now = pq.top();
		pq.pop();
		if(dis[now.id][now.flag] != now.len)
			continue;
		s.erase(now.id);

		if(now.flag)
		{
			cnt++;
			vector<int> del;

			for(const edge &i: a[now.id])
				bel[i.id] = cnt;
			
			for(int i: s)
			{
				if(bel[i] != cnt)
					del.push_back(i);
				if(bel[i] == cnt || dis[i][0] <= now.len)
					continue;

				dis[i][0] = now.len;
				pq.push({i, now.len, 0});
			}

			for(int i: del)
				s.erase(i);

			for(const edge &i: a[now.id])
			{
				int len = now.len + i.len - K;
				if(dis[i.id][i.flag] > len)
				{
					dis[i.id][i.flag] = len;
					pq.push({i.id, len, i.flag});
				}
			}
		}
		else
		{
			for(const edge &i: a[now.id])
			{
				if(dis[i.id][i.flag] > now.len + i.len)
				{
					dis[i.id][i.flag] = now.len + i.len;
					pq.push({i.id, now.len+i.len, i.flag});
				}
			}
		}
	}
}

void solve()
{
	int n, m, start;
	long long k;
	cin >> n >> m >> start >> k;

	pq = priority_queue<edge>();
	s = set<int>();
	for(int i=1; i<=n; i++)
	{		
		a[i].clear();
		dis[i][0] = dis[i][1] = 1e18;
		bel[i] = 0;
		s.insert(i);
	}

	for(int i=0, w, x, y, z; i<m; i++)
	{
		cin >> w >> x >> y >> z;
		a[w].push_back({x, 1LL*y, z});
	}

	dijk(start, k);
	const long long INF = 1e18;
	for(int i=1; i<=n; i++)
	{
		long long len = min(dis[i][0], dis[i][1]);
		cout << (len==INF? -1: len) << " ";
	}
	cout << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int tc;
	cin >> tc;
	while(tc--)
		solve();
}