#include "escape_route.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define sz size()
#define F first
#define S second
using namespace std;
const int N=1e6+3;
const ll inf=1e18;
ll start[N];// when security inspection start on edge
ll len[N];// length of edge
vector<pair<int,int>>g[N];// our graph [vertex , index of edge]
int n;// number of vertex
ll day;
void add_edge(int A,int B,int id){
g[A].push_back({B,id});
g[B].push_back({A,id});
}
ll calc(int s,int f,ll t){
vector<ll>p(n+3,inf);
p[s]=t;
set<pair<ll,int>>st;
st.insert({p[s],s});
while(!st.empty()){
int v=st.begin()->S;
st.erase(st.begin());
for(auto [to,i]:g[v]){
ll val=inf;
if((p[v]%day)+len[i]<=start[i])val=p[v]+len[i];
else val=(p[v]/day+1)*day+len[i];
if(p[to]>val){
st.erase({p[to],to});
p[to]=val;
st.insert({p[to],to});
}
}
}
// for(int i=0;i<n;i++)cout<<p[i]<<" ";
// cout<<"\n";
return p[f]-t;
}
std::vector<long long> calculate_necessary_time(
signed N, signed M, long long S, signed Q, std::vector<signed> A, std::vector<signed> B,
std::vector<long long> L, std::vector<long long> C, std::vector<signed> U,
std::vector<signed> V, std::vector<long long> T)
{
ios_base::sync_with_stdio(0);cin.tie(0);
day=S;
n=N;
// cout<<day<<" "<<n<<"\n";
int m=M,q=Q;
vector<ll>ans;
for(int i=0;i<m;i++){
// cout<<A[i]<<" "<<B[i]<<" "<<i<<"\n";
add_edge(A[i],B[i],i);
start[i]=C[i];
len[i]=L[i];
}
// for(int i=0;i<n;i++){
// for(auto [to,ii]:g[i])cout<<i<<"-"<<to<<" "<<ii<<"\n";
// }
for(int i=0;i<q;i++){
ans.push_back(calc(U[i],V[i],T[i]));
}
return ans;
}
// signed main(){
// int N,M;ll S;int Q;
// vector<int>A(M+3),B(M+3),U(Q+3),V(Q+3);
// vector<ll>L(M+3),C(M+3),T(Q+3);
// cin>>N>>M>>S>>Q;
// for(int i=0;i<M;i++)cin>>A[i]>>B[i]>>L[i]>>C[i];
// for(int i=0;i<Q;i++)cin>>U[i]>>V[i]>>T[i];
// vector<ll>ans=calculate_necessary_time(N,M,S,Q,A,B,L,C,U,V,T);
// for(auto to:ans)cout<<to<<"\n";
// }
