#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,q;
long long s;
vector<pair<int,pair<long long,long long>>>g[MAX_N];
void dijkstra(int start)
{
for(int i=1;i<=n;i++)dist[start][i]=INF;
priority_queue<pair<long long,int>>q;
q.push({0,start});
dist[start][start]=0;
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> U,
std::vector<int> V, std::vector<long long> T)
{
n=N;
m=M;
s=S;
q=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}});
}
for(int i=1;i<=n;i++)dijkstra(i);
vector<long long>anses;
for(int i=0;i<q;i++)
{
int u=U[i];
int v=V[i];
long long t=T[i];
long long ans=dist[u][v];
anses.push_back(ans);
}
return anses;
}
