#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cassert>

using namespace std;

const int MAXN = (int) 1e5 + 10;
int n, K, X, m, start;
const long long INF = (long long) 1e18;
vector<pair<int, int> > g[MAXN];

vector<long long> dijakstra() {
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			if (i != j) {
				g[i].push_back(make_pair(j, X));
			}
		}
	}
	vector<long long> d(n);
	for (int i = 0; i < n; i++) {
		d[i] = INF;
	}
	d[start] = 0;
	set<pair<long long, int> > st;
	st.insert(make_pair(0, start));
	while (!st.empty()) {
		int from = st.begin()->second;
    //cerr << "from " << from << " " << d[from] << endl;
		assert(st.find(make_pair(d[from], from)) != st.end());
		st.erase(make_pair(d[from], from));
		for (auto it: g[from]) {
			int to = it.first;
			int wt = it.second;
			if (d[to] > d[from] + wt) {
				//cerr << "to " << to << endl;
				st.erase(make_pair(d[to], to));
				d[to] = d[from] + wt;
				st.insert(make_pair(d[to], to));
			}
		}
	}
	return d;
}

void update(int from, int to, int wt, set<pair<long long, int> > &cliqueSet, set<pair<long long, int> > &st, vector<long long> &d) {
	if (d[to] > d[from] + wt) {
		//cerr << "to " << to << endl;
		if (to < K) {
			//fprintf(stderr, "to = %d, d[to] = %lld\n", to, d[to]);
			assert(cliqueSet.find(make_pair(d[to], to)) != cliqueSet.end());
			cliqueSet.erase(make_pair(d[to], to));
		}
		if (st.find(make_pair(d[to], to)) != st.end()) {
			st.erase(make_pair(d[to], to));
		}
		d[to] = d[from] + wt;
		st.insert(make_pair(d[to], to));
		if (to < K) {
			cliqueSet.insert(make_pair(d[to], to));
		}	
	}
}

vector<long long> smartDijakstra() {
	vector<long long> d(n);
	for (int i = 0; i < n; i++) {
		d[i] = INF;
	}
	d[start] = 0;
	set<pair<long long, int> > cliqueSet;
	for (int i = 0; i < K; i++) {
		cliqueSet.insert(make_pair(d[i], i));
	}
	set<pair<long long, int> > st;
	st.insert(make_pair(0, start));
	while (!st.empty()) {
		int from = st.begin()->second;
    //cerr << "from " << from << " " << d[from] << endl;
		assert(st.find(make_pair(d[from], from)) != st.end());
		st.erase(make_pair(d[from], from));
		for (auto it: g[from]) {
			int to = it.first;
			int wt = it.second;
			update(from, to, wt, cliqueSet, st, d);
		}
		if (from < K) {
			/*
			cerr << "here " << endl;
			for (auto it: cliqueSet) {
				cerr << it.second << " ";
			}
			cerr << endl;
			*/
			//auto iter = lower_bound(cliqueSet.begin(), cliqueSet.end(), make_pair(d[from] + X, -(int) 1e9));
			auto iter = cliqueSet.lower_bound(make_pair(d[from] + X, -(int) 1e9));
      vector<int> tos;
			for (auto it = iter; it != cliqueSet.end(); it++) {
				tos.push_back(it->second);
			}
			for (int to: tos) {
				int wt = X;
				//cerr << " to " << to  << " wt " << wt << endl;
				update(from, to, wt, cliqueSet, st, d);		
			}
		}
	}
	return d;
}

int main() {
  int T;
  scanf("%d", &T);
  assert(T >= 1 && T <= 3);
  int sum = 0;
  while (T--) {
  	scanf("%d %d %d %d %d", &n, &K, &X, &m, &start);
  	start--;
  	for (int i = 0; i < m; i++) {
  		int from, to, wt;
  		scanf("%d %d %d", &from, &to, &wt);
  		from--; to--;
  		g[from].push_back(make_pair(to, wt));
  		g[to].push_back(make_pair(from, wt));	
  	}
  	vector<long long> d = smartDijakstra();
  	for (int i = 0; i < n; i++) {
  		printf("%lld ", d[i]);
  	}
  	printf("\n");
  	for (int i = 0; i < n; i++) {
  		g[i].clear();
  	}
  }
  return 0;
}