#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int N = 1e5 + 10;
const int MOD = 1e9 + 7;
const LL INF = 1e18;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

struct node {
    int nex;
    int val, ops;
};
struct edge {
    LL dis;
    int idx, ops;
    bool operator < (const edge &B) const {
        return dis > B.dis;
    }
};
inline void solve() {
    int n, m; cin >> n >> m;
    int S, K; cin >> S >> K;
    vector<node> g[n + 1];
    while (m -- ) {
        int u, v, w, ops;
        cin >> u >> v >> w >> ops;
        g[u].push_back({v, w, ops});
    }
    set<int> s;
    for (int i = 1; i <= n; i ++ ) if (i != S) s.insert(i);
    priority_queue<edge, vector<edge>> q;
    vector<vector<LL>> dis(n + 1, vector<LL>(2, INF));
    vector<vector<bool>> vis(n + 1, vector<bool>(2));
    vector<bool> st(n + 1);
    dis[S][0] = 0;
    q.push({dis[S][0], S, 0});
    LL last = 0;
    while (!q.empty()) {
        auto t = q.top(); q.pop();
        int u = t.idx, ops = t.ops;
        if (ops == 1) {
            for (auto ite : g[u]) st[ite.nex] = true;
            vector<int> tmp;
            for (auto ite : s) {
                if (st[ite]) continue;
                dis[ite][0] = dis[u][1];
                q.push({dis[ite][0], ite, 0});
                tmp.push_back(ite);
            }
            for (auto ite : tmp) s.erase(ite);
            for (auto ite : g[u]) st[ite.nex] = false;
        } else s.erase(u);

        if (vis[u][ops]) continue;
        vis[u][ops] = true;
        assert(dis[u][ops] >= last);
        last = dis[u][ops];
        for (auto ite : g[u]) {
            int v = ite.nex, w = ite.val - (ops == 1 ? K : 0);
            if (dis[v][ite.ops] > dis[u][ops] + w) {
                dis[v][ite.ops] = dis[u][ops] + w;
                q.push({dis[v][ite.ops], v, ite.ops});
            }
        }
    }
    for (int i = 1; i <= n; i ++ ) {
        LL res = min(dis[i][0], dis[i][1]);
        if (res == INF) cout << -1 << ' ';
        else cout << res << ' ';
    }
    cout << endl;
}
signed main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}