#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int N = 1e5;
vector<pair<int, int>> g[N];

bool visited[N];
long long d[N];

int main() {
    int t; 
    cin >> t;
    while (t--) {
        int n, k, x, m, s;
        cin >> n >> k >> x >> m >> s;
        --s;
        for (int i = 0; i < n; ++i) {
            g[i].clear();
            visited[i] = false;
        }
        for (int i = 0; i < m; ++i) {
            int v, u, c;
            cin >> v >> u >> c;
            --v, --u;
            g[v].push_back(make_pair(u, c));
            g[u].push_back(make_pair(v, c));
        }
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
        for (int i = 0; i < n; ++i) {
            d[i] = 1e18;
        }
        d[s] = 0;
        q.push(make_pair(d[s], s));
        bool clique_explored = false;
        while (!q.empty()) {
            const int v = q.top().second;
            q.pop();
            if (visited[v]) continue;
            visited[v] = true;
            if (!clique_explored && v < k) {
                for (int u = 0; u < k; ++u) {
                    if (u == v) continue;
                    if (d[v]+x < d[u]) {
                        d[u] = d[v]+x;
                        q.push(make_pair(d[u], u));
                    }
                }
                clique_explored = true;
            }
            for (const auto& p : g[v]) {
                int u = p.first;
                int c = p.second;
                if (d[v]+c < d[u]) {
                    d[u] = d[v]+c;
                    q.push(make_pair(d[u], u));
                }
            }
        }
        for (int i = 0; i < n; ++i) {
            cout << d[i] << " ";
        }
        cout << endl;
    }
}