#include "iostream"
#include "cstring"
#include "cstdio"
#include "algorithm"
#include "queue"
#include "vector"
#include "queue"
#include "stack"
#include "ctime"
#include "set"
#include "map"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int P = 998244353;
const int MAXN = 2e5 + 10;
int n , m , S , K;

namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)
inline int rd() {
  int x = 0, f = 1;
  char c = gc();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = gc();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
  return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
inline void push(const char &c) {
  if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
  *pp++ = c;
}
inline void write(int x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) push(sta[--top] + '0');
  push( 10 );
}
}

struct ed {
	int v , w , t;
};
vector<ed> G[MAXN];
map<int,int> M[MAXN];

int vis[MAXN];
ll dis[MAXN];
vi lef;
void solve() {
	using namespace IO;
	n = rd() , m = rd() , S = rd() , K = rd();
	rep( i , 1 , m ) {
		int u , v , w , t;
		u = rd() , v = rd() , w = rd() , t = rd();
		M[u][v] = 1;
		G[u].pb( (ed) { v , w , t } );
	}
	priority_queue<pair<ll,int>> Q;
	rep( i , 1 , n * 2 ) dis[i] = 0x3f3f3f3f3f3f3f3f;
	dis[S] = 0;
	Q.push( mp( 0 , S ) );
	rep( u , 1 , n ) lef.pb( u );
	while( !Q.empty() ) {
		int u = Q.top().se; Q.pop();
		if( vis[u] ) continue;
		vis[u] = 1;
		int flg = 0;
		int tu = u;
		if( u > n ) {
			tu -= n;
			flg = 1;
			for( int i = 0 ; i < lef.size() ; ++ i ) {
				int v = lef[i];
				if( !M[tu].count( v ) ) {
					if( dis[v] > dis[u] ) {
						dis[v] = dis[u];
						Q.push( mp( -dis[u] , v ) );
					}
					swap( lef[i] , lef.back() );
					lef.pop_back();
					-- i;
				}
			}
		}
		for( auto t : G[tu] ) {
			int v = t.v;
			if( t.t ) v += n;
			if( dis[v] > dis[u] + t.w + ( flg ? -K : 0 ) ) {
				dis[v] = dis[u] + t.w + ( flg ? -K : 0 );
				Q.push( mp( -dis[v] , v ) );
			}
		}
//		rep( i , 1 , n ) printf("%lld ",dis[i]); puts("");
	}
	rep( i , 1 , n ) printf("%lld ",min( dis[i] , dis[i + n] ) > 1e18 ? -1ll : min( dis[i] , dis[i + n] )); puts("");
	rep( i , 1 , n * 2 ) vis[i] = 0 , M[i].clear() , G[i].clear();
	lef.clear();
}

signed main() {
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;T = IO::rd();while( T-- ) solve();
//	solve();
}