#include "escape_route.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll inf = 5e17;
vector<ll> calculate_necessary_time(int n, 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){
vector<ll> ans(q);
vector<vector<tuple<int, ll, ll>>> v(n);
for(int i = 0; i < m; i++){
v[A[i]].pb({B[i], L[i], C[i]});
v[B[i]].pb({A[i], L[i], C[i]});
}
for(int qq = 0; qq < q; qq++){
vector<ll> dis(n, inf);
vector<bool> bl(n, 0);
priority_queue<pair<ll, int>> pq;
dis[U[qq]] = T[qq];
pq.push({-T[qq], U[qq]});
while(!pq.empty()){
int nd = pq.top().sc; pq.pop();
if(bl[nd]) continue;
bl[nd] = 1;
for(auto [x, l, c]: v[nd]) if((dis[nd]%S+l<=c ? dis[nd]+l:((dis[nd]+S-1)/S)*S+l) < dis[x]){
dis[x] = (dis[nd]%S+l<=c ? dis[nd]+l:((dis[nd]+S-1)/S)*S+l);
pq.push({-dis[x], x});
}
}
ans[qq] = dis[V[qq]]-T[qq];
}
return ans;
}
