#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace my {
const int N = 92;
const ll INF = 1e18;
struct edge {
ll u;
ll w;
ll h;
edge(ll x, ll y, ll z) : u(x), w(y), h(z) {}
operator int() {
return u;
}
};
int n;
ll s;
vector<edge> g[N];
ll dist[N];
bool used[N];
ll near(int h) {
return (h + s - 1) / s * s;
}
ll query(ll v, ll to, ll t) {
fill_n(dist, N, INF);
fill_n(used, N, false);
dist[v] = t;
for (int it = 0; it < n; ++it) {
v = -1;
for (int i = 0; i < n; ++i) {
if (used[i]) {
continue;
}
if (v == -1 || dist[v] > dist[i]) {
v = i;
}
}
used[v] = true;
for (edge u : g[v]) {
ll can = dist[v] + u.w;
if (can % s > u.h || (can / s) > (dist[v] / s)) {
can = near(dist[v]) + u.w;
}
// cout << v << " " << u << " " << dist[v] << " " << can << endl;
if (dist[u] > can) {
dist[u] = can;
}
}
}
return dist[to] - t;
}
}
vector<ll> calculate_necessary_time(
int nn, 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) {
using namespace my;
n = nn, s = S;
for (int i = 0; i < M; ++i) {
g[A[i]].emplace_back(B[i], L[i], C[i]);
g[B[i]].emplace_back(A[i], L[i], C[i]);
}
vector<ll> ans(Q);
for (int i = 0; i < Q; ++i) {
ans[i] = query(U[i], V[i], T[i]);
}
return ans;
}
