#include "escape_route.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 92;
struct node{
long long w , lim;
int to;
};
vector < node > g[N];
vector<long long> calculate_necessary_time(int n, int m, long long s, int q, vector<int> a, vector<int> b,vector<long long> l, vector<long long> c, vector<int> v,vector<int> u, vector<long long> t){
vector < long long > ans;
for(int i = 0; i < m; i++){
g[a[i]].pb({l[i] , c[i] , b[i]});
g[b[i]].pb({l[i] , c[i] , a[i]});
}
for(int i = 0; i < q; i++){
set < pair < pair < int , long long > , int > > st;
st.insert({{0 , t[i]} , v[i]});
pair < int , long long > dst[n];
for(int i = 0; i < n; i++) dst[i] = {n + 1 , n + 1};
dst[v[i]] = {0 , t[i]};
while(st.size()){
int v = st.begin() -> second;
st.erase(st.begin());
for(node it : g[v]){
int d = dst[v].first , tim = dst[v].second;
if(0 <= tim && tim <= it.lim - it.w){
tim += it.w;
}
else{
tim = it.w;
d++;
}
if(dst[it.to].first > d || dst[it.to].first == d && dst[it.to].second > tim){
st.erase({dst[it.to] , it.to});
dst[it.to] = {d , tim};
st.insert({dst[it.to] , it.to});
}
}
}
ans.pb(dst[u[i]].first * s + dst[u[i]].second - t[i]);
}
return ans;
}
// int main(){
// int n , m;
// long long s;
// int q;
// cin >> n >> m >> s >> q;
// vector < int > a , b;
// vector < long long > l , c;
// for(int i = 0; i < m; i++){
// int x , y , z , t;
// cin >> x >> y >> z >> t;
// a.pb(x);
// b.pb(y);
// l.pb(z);
// c.pb(t);
// }
// vector < int > v , u;
// vector < long long > t;
// for(int i = 0; i < q; i++){
// int x , y , z;
// cin >> x >> y >> z;
// v.pb(x);
// u.pb(y);
// t.pb(z);
// }
// vector < long long > ans = calculate_necessary_time(n , m , s , q , a , b , l , c , v , u , t);
// for(auto it : ans){
// cout << it << '\n';
// }
// }
