/****************
 *@description:for the Escape Project
 *@author: Nebula_xuan
 * @Date: 2022-07-21 20:49:34
 *************************************************************************/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
using namespace std;
#define rep(h, t) for (int i = h; i <= t; i++)
#define dep(t, h) for (int i = t; i >= h; i--)

typedef pair<int, int> PII;
typedef long long ll;
const int N = 5e5 + 10;
const int M = N * 2;
int n, m, s, k;
ll dist[N][2];
bool st[N][2];
int vis[N];
int h[N], ne[M], e[M], w[M], p[M], idx;
struct node
{
    ll a, b, p;
    bool operator<(const node &w) const
    {
        return b > w.b;
    }
};
void add(int a, int b, int c, int d)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, p[idx] = d, h[a] = idx++;
}
void dijkstra()
{
    set<int> S;
    rep(1, n)
    {
        if (i != s)
            S.insert(i);
        st[i][0] = st[i][1] = false;
        dist[i][0] = dist[i][1] = 1e18;
    }
    dist[s][0] = 0;
    priority_queue<node> q;
    q.push({s, 0, 0});
    int cnt = 0;
    while (q.size())
    {
        auto t = q.top();
        q.pop();
        int ver = t.a, tp = t.p;
        cnt++;
        if (!tp)
            S.erase(ver);
        else
        {
            for (int i = h[ver]; i != -1; i = ne[i])
            {
                int j = e[i];
                vis[j] = cnt;
            }
            vector<int> v;
            for (auto it : S)
            {
                if (vis[it] != cnt)
                {
                    dist[it][0] = dist[ver][1];
                    q.push({it, dist[it][0], 0});
                    v.push_back(it);
                }
            }
            for (auto it : v)
                S.erase(it);
        }
        int y = 0;
        if (tp)
            y -= k;
        if (st[ver][tp])
            continue;
        else
            st[ver][tp] = 1;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j][p[i]] > dist[ver][tp] + w[i] + y)
            {
                dist[j][p[i]] = dist[ver][tp] + w[i] + y;
                q.push({j, dist[j][p[i]], p[i]});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)
    {
        idx = 0;
        cin >> n >> m >> s >> k;
        rep(0, n)
        {
            h[i] = -1, vis[i] = 0;
        }
        rep(1, m)
        {
            int x, y, z, zz;
            cin >> x >> y >> z >> zz;
            add(x, y, z, zz);
        }
        dijkstra();
        rep(1, n)
        {
            if (min(dist[i][0], dist[i][1]) != 1e18)
                cout << min(dist[i][0], dist[i][1]) << " ";
            else
                cout << "-1 ";
        }
        cout << endl;
        //  puts("");
    }
}