#include <bits/stdc++.h>
#define N 1000005
using i64 = long long;
using namespace std;

int n, m, s, k, vis[2][N];
i64 dis[2][N];
vector<array<int, 3>> adj[N];
struct node
{
    int type, x;
    i64 dis;
    bool operator<(const node &tmp) const { return dis > tmp.dis; }
};
void solve()
{
    cin >> n >> m >> s >> k;
    set<int> st;
    for (int i = 1; i <= n; i++)
        st.insert(i);
    for (int i = 1, u, v, w, r; i <= m; i++)
    {
        cin >> u >> v >> w >> r;
        adj[u].push_back({v, w, r});
    }
    priority_queue<node> que;
    que.push({0, s, 0});
    fill(dis[0] + 1, dis[0] + n + 1, 1e18);
    fill(dis[1] + 1, dis[1] + n + 1, 1e18);
    fill(vis[0] + 1, vis[0] + n + 1, 0);
    fill(vis[1] + 1, vis[1] + n + 1, 0);
    dis[0][s] = 0;
    vector<int> col(n + 1);
    while (!que.empty())
    {
        auto [p, cur, _] = que.top();
        que.pop();
        if (vis[p][cur])
            continue;
        vis[p][cur] = 1;
        st.erase(cur);
        if (p)
        {
            for (const auto &[i, _, _1] : adj[cur])
                col[i] = cur;
            for (int i : st)
            {
                if (col[i] != cur)
                {
                    dis[0][i] = dis[p][cur];
                    que.push({0, i, dis[0][i]});
                }
            }
        }
        int d = p ? -k : 0;
        for (auto &t : adj[cur])
        {
            if (dis[t[2]][t[0]] > dis[p][cur] + d + t[1])
            {
                dis[t[2]][t[0]] = dis[p][cur] + d + t[1];
                que.push({t[2], t[0], dis[t[2]][t[0]]});
            }
        }
    }
    for (int i = 1; i <= n; i++)
    {
        i64 ans = min(dis[0][i], dis[1][i]);
        if (ans == 1e18)
            ans = -1;
        cout << ans << ' ';
        adj[i].clear();
    }
    cout << '\n';
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}