#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ALL(x) (x).begin(), (x).end()
#define len(x) (int(x.size()))
int N, M, Q;
ll S;
constexpr ll inf = 1ll << 60;
vector<vector<pair<ll, ll>>> edges;
vector<vector<ll>> table0;
void make_table0() {
table0.resize(N);
for (int origin = 0; origin < N; ++origin) {
auto &dist = table0[origin];
dist.assign(N, inf);
dist[origin] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>,
greater<pair<ll, int>>>
pq;
pq.push(make_pair(0, origin));
while (not pq.empty()) {
auto [nd, f] = pq.top();
pq.pop();
if (dist[f] < nd) continue;
ll clc = nd % S;
for (int t = 0; t < N; ++t) {
if (edges[f][t].second == -1) continue;
ll nxt = clc < edges[f][t].second
? nd + edges[f][t].first
: ((nd + S - 1) / S * S + edges[f][t].first);
if (dist[t] > nxt) {
dist[t] = nxt;
pq.push(make_pair(nxt, t));
}
}
}
}
}
vector<vector<ll>> times_vs;
vector<vector<vector<ll>>> table1;
vector<vector<vector<bool>>> opened;
vector<vector<int>> upd_orders;
vector<vector<int>> upd_levels;
vector<pair<ll, int>> upd_times;
ll cur_time;
void update(int origin, int f, int t) {
auto dist = table1[origin].back();
if (dist[t] > dist[f] + edges[f][t].first) {
dist[t] = dist[f] + edges[f][t].first;
ll nxt_time = cur_time + dist[t];
int p = upper_bound(ALL(times_vs[t]), nxt_time, greater()) -
times_vs[t].begin() - 1;
auto &t_dist = table1[t][p];
for (int i = 0; i < N; ++i) {
if (dist[i] > dist[t] + t_dist[i]) {
dist[i] = dist[t] + t_dist[i];
}
}
times_vs[origin].push_back(cur_time);
table1[origin].push_back(dist);
}
int mx = -1;
ll mx_time = -1;
for (int i = 0; i < N; ++i) {
int t = upd_orders[i][upd_levels[origin][i]];
if (edges[i][t].second == -1) continue;
ll time = edges[i][t].second - 1 - dist[i];
if (time <= inf / 2 and mx_time < time) {
mx_time = time;
mx = i;
}
}
upd_times[origin] = make_pair(mx_time, mx);
}
void make_table1() {
// naive
table1.resize(N);
opened = vector(N, vector(N, vector(N, false)));
times_vs.resize(N);
cur_time = S;
upd_orders.resize(N);
upd_levels.resize(N);
upd_times.resize(N);
for (int i = 0; i < N; ++i) {
upd_orders[i].resize(N);
iota(ALL(upd_orders[i]), 0);
sort(ALL(upd_orders[i]), [&](int a, int b) {
return edges[i][a].second > edges[i][b].second;
});
upd_levels[i].assign(N, 0);
}
for (int i = 0; i < N; ++i) {
table1[i] = vector<vector<ll>>{vector<ll>(N, inf)};
table1[i][0][i] = 0;
times_vs[i].push_back(S);
update(i, i, i);
}
while (true) {
int mx = -1;
ll mx_time = -1;
for (int i = 0; i < N; ++i) {
if (upd_times[i].first > mx_time) {
mx_time = upd_times[i].first;
mx = i;
}
}
if (mx == -1) break;
ll time = mx_time, origin = mx, f = upd_times[origin].second;
int t = upd_orders[f][upd_levels[origin][f]];
++upd_levels[origin][f];
opened[origin][f][t] = true;
cur_time = min(cur_time, time);
update(origin, f, t);
}
for (int origin = 0; origin < N; ++origin) {
reverse(ALL(times_vs[origin]));
reverse(ALL(table1[origin]));
}
}
std::vector<long long> calculate_necessary_time(
int n, int m, long long s, int q, std::vector<int> A, std::vector<int> B,
std::vector<long long> L, std::vector<long long> C, std::vector<int> U,
std::vector<int> V, std::vector<long long> T) {
N = n, M = m, S = s, Q = q;
edges.assign(N, vector<pair<ll, ll>>(N, make_pair(inf, -1)));
for (int i = 0; i < M; ++i) {
edges[A[i]][B[i]] = edges[B[i]][A[i]] = make_pair(L[i], C[i] - L[i] + 1);
}
make_table0();
make_table1();
vector<ll> ans(Q);
for (int i = 0; i < Q; ++i) {
int u = U[i], v = V[i];
ll t = T[i];
int p = (lower_bound(ALL(times_vs[u]), t) - times_vs[u].begin());
auto &dist = table1[u][p];
if (dist[v] != inf) {
ans[i] = dist[v];
} else {
ll res = inf;
for (int i = 0; i < N; ++i) {
if (dist[i] != inf) {
res = min(res, (S - t) + table0[i][v]);
}
}
ans[i] = res;
}
}
return ans;
}
