#include"escape_route.h"
#include<iostream>
#include<cstdio>
#include<cmath>
#define SN 90
#define SM 3000000
using namespace std;
const long long inf=(long long)(1e18);
struct reads
{
	int num;
	long long data;
};
vector<reads>st[SN+1][SN+1];
long long tS,ans[SM+1],dis[SN+1],cst[SN+1][SN+1],leng[SN+1][SN+1];
bool used[SN+1][SN+1],vis[SN+1];
int n;
long long F(int x,int y,long long t)
{
	int rt;
	long long minn;
	for (int i=1;i<=n;++i) dis[i]=inf,vis[i]=0;
	dis[x]=t;
	for (int i=1;i<=n;++i)
	{
		minn=inf;
		for (int j=1;j<=n;++j)
			if (!vis[j]&&dis[j]<minn)
				rt=j,minn=dis[j];
		vis[rt]=1;
		for (int j=1;j<=n;++j)
			if (used[rt][j])
			{
				if (minn%tS<=cst[rt][j]-leng[rt][j]) dis[j]=min(dis[j],minn+leng[rt][j]);
				else dis[j]=min(dis[j],(minn/tS+1)*tS+leng[rt][j]);
			}
	}
	return dis[y]-t;
}
void solve(int x,int y,long long l,long long r,long long L,long long R,vector<reads>p)
{
	if (p.empty()) return;
	if (L==R)
	{
		for (int i=0;i<p.size();++i) ans[p[i].num]=L;
		return;
	}
	long long mid=(l+r)>>1,d=F(x,y,mid),d2=F(x,y,mid+1);
	vector<reads>A;
	vector<reads>B;
	for (int i=0;i<p.size();++i)
	{
		if (p[i].data<=mid) A.push_back(p[i]);
		else B.push_back(p[i]);
	}
	solve(x,y,l,mid,L,d,A),solve(x,y,mid+1,r,d2,R,B);
	return;
}
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>U,vector<int>V,vector<long long>T)
{
	int rt;
	long long minn,t;
	vector<long long>p;
	n=N,tS=S;
	for (int i=1;i<=M;++i) A[i-1]++,B[i-1]++,used[A[i-1]][B[i-1]]=used[B[i-1]][A[i-1]]=1,cst[A[i-1]][B[i-1]]=cst[B[i-1]][A[i-1]]=C[i-1],leng[A[i-1]][B[i-1]]=leng[B[i-1]][A[i-1]]=L[i-1];
	for (int i=1;i<=Q;++i) U[i-1]++,V[i-1]++,st[U[i-1]][V[i-1]].push_back((reads){i,T[i-1]});
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			solve(i,j,0,S-1,F(i,j,0),F(i,j,S-1),st[i][j]);
	for (int i=1;i<=Q;++i) p.push_back(ans[i]);
	return p;
}