#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define fr first
#define sc second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define all(s) (s).begin(), (s).end()
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) < (y) ? (y) : (x))

inline int rd() {
    int x = 0;
    bool f = 0;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) f |= (c == '-');
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    return f ? -x : x; 
}

#define N 1000007

int tot, hd[N];

struct edge{int to, nxt, w, ty;} e[N];

ll dis[N][2];

inline void add() {
    int u = rd();
    e[++tot].to = rd(); e[tot].w = rd(); 
    e[tot].ty = rd(); e[tot].nxt = hd[u]; hd[u] = tot;
}

bool vis[N][2];

int K;

#define zzk pair<ll, pair<int, int> > 

priority_queue<zzk > q;

vector<int> nov, tmpv;

bool tmpvis[N];

inline void dij(int s) {
    dis[s][0] = 0;
    q.push(mp(0, mp(s, 0)));
    while (!q.empty()) {
        zzk tmp = q.top(); q.pop();
        int u = tmp.sc.fr, ty = tmp.sc.sc;
        //printf("nw at %d %d\n", u, ty);

        if (vis[u][ty]) continue; vis[u][ty] = true;
        if (ty) {
            for (int i = hd[u], v; i; i = e[i].nxt) {
                tmpvis[v = e[i].to] = 1;
                if (dis[v][e[i].ty] > dis[u][1] + e[i].w - K) {
                    dis[v][e[i].ty] = dis[u][1] + e[i].w - K;
                    q.push(mp(-dis[v][e[i].ty], mp(v, e[i].ty)));
                }
            }
            for (auto v : nov)
                if (!tmpvis[v]) {
                    if (dis[v][0] > dis[u][1]) {
                        dis[v][0] = dis[u][1];
                        q.push(mp(-dis[v][0], mp(v, 0)));
                    }
                }
            for (auto v : nov)
                if (tmpvis[v]) tmpv.push_back(v);
            nov = tmpv; tmpv.clear();
            for (int i = hd[u]; i; i = e[i].nxt) tmpvis[e[i].to] = 0;
        } else {
            for (int i = hd[u], v; i; i = e[i].nxt)
                if (dis[v = e[i].to][e[i].ty] > dis[u][0] + e[i].w) {
                    dis[v][e[i].ty] = dis[u][0] + e[i].w;
                    q.push(mp(-dis[v][e[i].ty], mp(v, e[i].ty)));
                }
        }
    }
}

inline void work() {
    tot = 0;
    int n = rd(), m = rd(), s = rd(); K = rd();
    nov.clear();
    for (int i = 1; i <= n; ++i) {
        nov.push_back(i);
        hd[i] = 0; 
        vis[i][0] = vis[i][1] = 0;
        dis[i][0] = dis[i][1] = 1e18;
    }
    for (int i = 1; i <= m; ++i) add();
    dij(s);
    for (int i = 1; i <= n; ++i) {
        ll ans = min(dis[i][0], dis[i][1]); 
        printf("%lld ", ans >= 1e18 ? -1 : ans); 
    }
    puts("");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}