#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include "escape_route.h"
using namespace std;
const int MAX_N=1e2+2;
const long long INF=(1LL<<60);
long long dist[MAX_N][MAX_N];//start at time zero
int n,m,queries;
long long s;
vector<pair<int,pair<long long,long long>>>g[MAX_N];
void dijkstra(int start,long long t)
{
for(int i=0;i<n;i++)dist[start][i]=INF;
priority_queue<pair<long long,int>>q;
q.push({-t,start});
dist[start][start]=t;
while(q.size())
{
auto top=q.top();
q.pop();
long long curdist=-top.first;
int u=top.second;
if(curdist!=dist[start][u])continue;
for(auto [v,vals]:g[u])
{
long long len=vals.first;
long long c=vals.second;
long long cost=len;
if(curdist%s>c-len)
{
cost+=(s-curdist%s);
}
if(curdist+cost<dist[start][v])
{
dist[start][v]=curdist+cost;
q.push({-dist[start][v],v});
}
}
}
}
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> UU,
std::vector<int> VV, std::vector<long long> TT)
{
n=N;
m=M;
s=S;
queries=Q;
for(int i=0;i<m;i++)
{
int u=A[i],v=B[i];
long long l=L[i],c=C[i];
g[u].push_back({v,{l,c}});
g[v].push_back({u,{l,c}});
}
//cout<<"\n";
//cout<<UU[0]<<" 3453\n";
//for(int i=1;i<=n;i++)dijkstra(i,0);
vector<long long>anses;
for(int i=0;i<queries;i++)
{
int uu=UU[i];
int vv=VV[i];
long long tt=TT[i];
dijkstra(uu,tt);
long long ans=dist[uu][vv];
//cout<<uu<<" "<<vv<<" "<<tt<<"\n";
anses.push_back(ans);
}
return anses;
}
