#include "escape_route.h"
using namespace std;
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
// #define int long long
struct edge {
long long to, d, c;
};
std::vector<long long> calculate_necessary_time(int N, int M, long long S, int Q, vector<int> A, vector<int> B, vector<long long> L, vector<long long> C, std::vector<int> U, std::vector<int> V, std::vector<long long> T) {
vector<vector<edge>> adj(N);
for (int i = 0; i < M; i++) {
int u, v, d, c;
u = A[i]; v = B[i]; d = L[i]; c = C[i];
adj[u].pb({v, d, c});
adj[v].pb({u, d, c});
}
vector<long long> ans(Q, 0);
for (int i = 0; i < Q; i++) {
int u, v, t;
u = U[i]; v = V[i]; t = T[i];
// cout << "Q: " << u << " " << v << " " << t << '\n';
vector<long long> dist(N, 1e18); dist[u] = t;
set<pair<long long, long long>> dijk; dijk.insert({t, u});
while (dijk.size()) {
auto cur = *dijk.begin();
dijk.erase(dijk.begin());
long long curd = cur.first; int node = cur.second;
// cout << node << " node " << curd << " curd\n";
if (dist[node] < curd) continue;
for (auto &e : adj[node]) {
long long to = e.to, d = e.d, c = e.c;
long long aft;
if (curd%S + d <= c) aft = d;
else aft = d + S - curd%S;
if (aft+curd < dist[to]) {
dijk.erase({dist[to], to});
dist[to] = aft + curd;
dijk.insert({dist[to], to});
}
}
}
ans[i] = dist[v] - T[i];
}
return ans;
}
