#include "escape_route.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
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) {
vector<ll> ans(Q);
vector<vector<ll>> queries(N);
for(int i=0; i<Q; ++i) {
queries[U[i]].push_back(i);
}
vector<vector<pair<int, int>>> g(N);
for(int i=0; i<M; ++i) {
g[A[i]].push_back({B[i], i});
g[B[i]].push_back({A[i], i});
}
ll inf = 1e18;
for(int s=0; s<N; ++s) {
for(auto idx : queries[s]) {
vector<ll> dist(N, inf), vis(N,0);
dist[s] = T[idx];
while(1) {
pair<ll, ll> best = {inf,0};
for(int i=0; i<N; ++i) if(!vis[i]) best = min(best, {dist[i], i});
if(best.first == inf) break;
auto[dv,v] = best;
vis[v] = 1;
for(auto[u,k] : g[v]) {
ll w = L[k];
if(dv > C[k] - L[k]) w += S-dv;
if(dist[u] > dist[v] + w) {
dist[u] = dist[v] + w;
}
}
}
ans[idx] = dist[V[idx]];
}
}
return ans;
}
