#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 90 + 7;
const ll inf = 1e18;
int n;
vector<array<ll, 4>> g[N];
ll zero_delay[N][N], f[N * N][N][N];
vector<int> qs[N];
vector<ll> calculate_necessary_time(int N, int M, ll S, int Q, vector<int> A, vector<int> B, vector<ll> L, vector<ll> C, vector<int> U, vector<int> V, vector<ll> T) {
for (int i = 0; i < M; ++i) {
g[A[i]].push_back({B[i], L[i], C[i], i});
g[B[i]].push_back({A[i], L[i], C[i], i});
}
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
zero_delay[u][v] = inf;
}
vector<bool> vis(N);
priority_queue<pair<ll, int>> pq;
pq.push({0, u});
zero_delay[u][u] = 0;
while (!pq.empty()) {
int x = pq.top().second;
pq.pop();
if (vis[x]) continue;
vis[x] = 1;
for (auto [v, l, c, id] : g[x]) {
ll cost = zero_delay[u][x] + l;
if (zero_delay[u][x] % S + l > c) {
cost += S - zero_delay[u][x];
}
if (cost < zero_delay[u][v]) {
zero_delay[u][v] = cost;
pq.push({-zero_delay[u][v], v});
}
}
}
}
for (int i = 0; i < M; ++i) {
for (int u = 0; u < N; ++u) {
for (int v = 0; v < N; ++v) {
f[i][u][v] = inf;
}
if (A[i] != u && B[i] != u) continue;
vector<bool> vis(N, 0);
f[i][u][u] = C[i] - L[i];
priority_queue<pair<ll, int>> pq;
pq.push({0, u});
while (!pq.empty()) {
int x = pq.top().second;
pq.pop();
if (vis[x]) continue;
vis[x] = 1;
for (auto [v, l, c, id] : g[x]) {
ll cost = f[i][u][x] + l;
if (f[i][u][x] % S + l > c) {
cost += S - f[i][u][x] % S;
}
if (cost < f[i][u][v]) {
f[i][u][v] = cost;
pq.push({-f[i][u][v], v});
}
}
}
for (int v = 0; v < N; ++v) {
if (f[i][u][v] <= S) {
f[i][u][v] -= (C[i] - L[i]);
} else {
f[i][u][v] = inf;
}
}
}
}
vector<ll> sol(Q, inf);
for (int i = 0; i < Q; ++i) {
qs[U[i]].push_back(i);
sol[i] = (T[i] == 0 ? 0 : S - T[i]) + zero_delay[U[i]][V[i]];
}
for (int u = 0; u < N; ++u) {
sort(g[u].begin(), g[u].end(), [&](array<ll, 4> a, array<ll, 4> b) {
return a[2] - a[1] > b[2] - b[1];
});
}
for (int u = 0; u < N; ++u) {
sort(qs[u].begin(), qs[u].end(), [&](int x, int y) {
return T[x] > T[y];
});
vector<int> ind(N, 0);
vector<ll> dist(N, inf);
dist[u] = 0;
int ptr = 0;
while (true) {
int who = -1;
ll best = -inf;
for (int x = 0; x < N; ++x) {
if (ind[x] == g[x].size()) continue;
if (g[x][ind[x]][2] - g[x][ind[x]][1] - dist[x] >= best) {
best = g[x][ind[x]][2] - g[x][ind[x]][1] - dist[x];
who = x;
}
}
while (ptr < qs[u].size() && T[qs[u][ptr]] > best) {
int id = qs[u][ptr];
ll ans = inf;
ans = min(ans, dist[V[id]]);
for (int v = 0; v < N; ++v) {
if (dist[v] < inf) {
ans = min(ans, S - T[id] + zero_delay[v][V[id]]);
}
}
sol[id] = min(sol[id], ans);
++ptr;
}
if (best < 0) break;
int id = g[who][ind[who]][3];
int to = g[who][ind[who]][0];
++ind[who];
for (int v = 0; v < N; ++v) {
if (f[id][who][v] + dist[who] < dist[v]) {
dist[v] = f[id][who][v] + dist[who];
}
}
}
}
return sol;
}
/**
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll N, M, S, Q;
cin >> N >> M >> S >> Q;
vector<int> A(M), B(M), U(Q), V(Q);
vector<ll> L(M), C(M), T(Q);
for (int i = 0; i < M; ++i) cin >> A[i] >> B[i] >> L[i] >> C[i];
for (int i = 0; i < Q; ++i) cin >> U[i] >> V[i] >> T[i];
vector<ll> sol = calculate_necessary_time(N, M, S, Q, A, B, L, C, U, V, T);
for (int i = 0; i < sol.size(); ++i) cout << sol[i] << "\n";
return 0;
}
**/
