// Author:  HolyK
// Created: Sat Sep  3 16:36:50 2022
#include <bits/stdc++.h>
#include <queue>

template <class T, class U>
inline bool smin(T &x, const U &y) {
  return y < x ? x = y, 1 : 0;
}
template <class T, class U>
inline bool smax(T &x, const U &y) {
  return x < y ? x = y, 1 : 0;
}

using LL = long long;
using PII = std::pair<int, int>;

void solve() {
  int n, m, s, k;
  std::cin >> n >> m >> s >> k;
  s--;
  std::set<int> v;
  std::vector<int> vis(n), d(n + 1), g(m);
  std::vector<std::array<int, 4>> e(m);
  int vn = 0;
  
  for (int i = 0; i < m; i++) {
    int x, y, w, t;
    std::cin >> x >> y >> w >> t;
    x--, y--;
    e[i] = {x, y, w, t};
    d[x]++;
  }
  for (int i = 1; i <= n; i++) d[i] += d[i - 1];

  for (int i = 0; i < m; i++) {
    g[--d[e[i][0]]] = i;
  }

  for (int i = 0; i < n; i++) {
    if (i != s) v.insert(i);
  }

  std::vector<LL> a(n * 2, 1e18);
  a[s] = 0;
  std::priority_queue<std::pair<LL, int>> q;
  q.push({0, s});

  std::vector<bool> qv(n * 2);
  while (!q.empty()) {
    int x = q.top().second;
    q.pop();
    if (qv[x]) continue;
    qv[x] = true;

    auto extend = [&](int y, int z) {
      if (smin(a[y], a[x] + z)) {
        q.push({-a[y], y});
      }
    };

    if (x >= n) {
      extend(x - n, 0);
      vn++;
      for (int i = d[x - n]; i < d[x + 1 - n]; i++) {
        vis[e[g[i]][1]] = vn;
      }
      for (auto it = v.begin(); it != v.end(); ) {
        if (vis[*it] == vn) {
          it++;
        } else {
          extend(*it, 0);
          it = v.erase(it);
        }
      }
    }

    int u, v;
    if (x >= n) {
      u = x - n;
      v = k;
    } else {
      u = x;
      v = 0;
    }
    for (int i = d[u]; i < d[u + 1]; i++) {
      int j = g[i], y = e[j][1], z = e[j][2] - v;
      if (e[j][3]) {
        extend(y + n, z);
      } else {
        extend(y, z);
      }
    }
  }

  for (int i = 0; i < n; i++) {
    if (a[i] == 1e18) a[i] = -1;
    std::cout << a[i] << " \n"[i == n - 1];
  }
}

int main() {
  // freopen("t.in", "r", stdin);
  
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  
  int t = 1;
  
  std::cin >> t;
  
  while (t--) {
    solve();
  }
  return 0;
}