#include "escape_route.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()
using namespace std;
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) {
ll n = N, m = M, tm = S, q = Q, d[2002];
vector <ll> ans;
vector <pair <ll, pair <ll, ll>>> g[2002];
for (int i = 0; i < m; i++){
g[A[i]].pb ({B[i], {L[i], C[i]}});
g[B[i]].pb ({A[i], {L[i], C[i]}});
}
for (int i = 0; i < n; i++){
random_shuffle (all (g[i]));
}
for (int i = 0; i < q; i++){
ll a = U[i], b = V[i], c = T[i];
set <pair <ll, ll>> s;
for (int i = 0; i < n; i++){
d[i] = 1e18;
}
d[a] = c;
s.insert ({d[a], a});
int cnt = 100;
while (cnt > 0 && s.size()){
pair <ll, ll> mn = *s.begin();
ll v = mn.S, w = mn.F;
cnt--;
s.erase (mn);
for (auto i: g[v]){
if (w % tm + i.S.F <= i.S.S && w + i.S.F < d[i.F]){
s.erase ({d[i.F], i.F});
d[i.F] = w + i.S.F;
s.insert ({d[i.F], i.F});
}
else if (w % tm + i.S.F > i.S.S){
a = (tm - w % tm) + i.S.F + w;
if (a < d[i.F]){
s.erase ({d[i.F], i.F});
d[i.F] = a;
s.insert ({d[i.F], i.F});
}
}
}
}
ans.pb (d[b] - c);
}
return ans;
}
