#include "escape_route.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
struct edg{
int pos;
lint L, C;
};
struct node{
int i, j; lint max_time;
bool operator<(const node &n)const{
return max_time < n.max_time;
}
};
lint daybreak[96][96];
lint dayfinish[96][96];
lint adj[96][96], dp[96][96];
vector<edg> gph[96];
vector<pi> prec[96][96];
lint S;
void do_prec(int s, int n){
priority_queue<pi, vector<pi>, greater<pi>> pq[96]; // (dist, weight)
pq[s].emplace(0, -S);
for(int i = 0; i < n; i++) prec[s][i].emplace_back(-1, 1);
while(true){
pi ans(1e18, 1e18);
for(int i = 0; i < n; i++){
while(sz(pq[i]) &&
(pq[i].top().first <= prec[s][i].back().first ||
-pq[i].top().second <= -prec[s][i].back().second)) pq[i].pop();
if(sz(pq[i])){
ans = min(ans, pi(pq[i].top().first, i));
}
}
if(ans.second > n) break;
int pos = ans.second;
prec[s][pos].push_back(pq[pos].top());
lint cur_dist = pq[pos].top().first;
lint cur_weight = -pq[pos].top().second;
pq[pos].pop();
for(auto &j : gph[pos]){
lint new_dist = cur_dist + j.L;
lint new_weight = min(cur_weight, j.C - new_dist);
if(new_weight < 0) continue;
pq[j.pos].emplace(new_dist, -new_weight);
}
}
for(int i = 0; i < n; i++){
for(auto &[x, y] : prec[s][i]){
// printf("prev %d %d %lld %lld\n", s, i, x, y);
tie(x, y) = pi(-y, x);
}
for(int j = 0; j < sz(prec[s][i])-1; j++){
prec[s][i][j].second = prec[s][i][j + 1].second;
}
prec[s][i].back().second = 1e18;
for(auto &[x, y] : prec[s][i]){
x++;
// printf("%d %d %lld %lld\n", s, i, x, y);
}
}
}
// wtf just use namespace std and pairs
std::vector<long long> calculate_necessary_time(
int N, int M, long long Sfuck, 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) {
S = Sfuck;
for(int i = 0; i < M; i++){
gph[A[i]].push_back({B[i], L[i], C[i]});
gph[B[i]].push_back({A[i], L[i], C[i]});
}
{
priority_queue<node> pq;
memset(daybreak, 0x3f, sizeof(daybreak));
auto enq = [&](int s, int e, lint x){
if(daybreak[s][e] > x){
daybreak[s][e] = x;
pq.push({s, e, -x});
}
};
for(int i = 0; i < N; i++){
enq(i, i, 0);
}
while(sz(pq)){
auto x = pq.top(); pq.pop();
x.max_time = -x.max_time;
if(daybreak[x.i][x.j] != x.max_time) continue;
for(auto &e : gph[x.j]){
if(x.max_time + e.L <= e.C){
enq(x.i, e.pos, x.max_time + e.L);
}
}
}
}
{
priority_queue<node> pq;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
dayfinish[i][j] = -1e18;
}
}
auto enq = [&](int s, int e, lint x){
if(dayfinish[s][e] < x){
dayfinish[s][e] = x;
pq.push({s, e, x});
}
};
for(int i = 0; i < N; i++){
enq(i, i, S);
}
while(sz(pq)){
auto x = pq.top(); pq.pop();
if(dayfinish[x.i][x.j] != x.max_time) continue;
for(auto &e : gph[x.i]){
lint val = min(x.max_time, e.C) - e.L;
if(val >= 0) enq(e.pos, x.j, val);
}
}
}
{
memset(adj, 0x3f, sizeof(adj));
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
if(dayfinish[i][j] >= 0) adj[i][j] = 1;
if(i == j) adj[i][j] = 0;
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
for(int k = 0; k < N; k++){
adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
assert(adj[i][j] <= N);
dp[i][j] = 1e18;
for(int k = 0; k < N; k++){
dp[i][j] = min(adj[i][k] * S + daybreak[k][j], dp[i][j]);
}
}
}
}
for(int i = 0; i < N; i++){
do_prec(i, N);
}
vector<lint> ans(Q);
for(int i = 0; i < Q; i++){
if(dayfinish[U[i]][V[i]] >= T[i]){
auto it = upper_bound(all(prec[U[i]][V[i]]), pi(T[i] + 1, -1));
ans[i] = prev(it)->second;
continue;
}
lint ret = 1e18;
for(int j = 0; j < N; j++){
if(dayfinish[U[i]][j] >= T[i]){
ret = min(ret, S - T[i] + dp[j][V[i]]);
}
}
ans[i] = ret;
}
return ans;
}
