#include "escape_route.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct edge
{
int v;
ll L, time;
};
struct query
{
ll time,add;
int a,b,ind;
bool operator<(const query& other) const
{
return time>other.time;
}
};
struct info
{
ll time;
ll dists[90];
info()
{
rep(i,90) dists[i] = 1e18;
}
bool operator<(const info& other) const
{
return time < other.time;
}
};
vl query_ans;
int n;
ll S;
vector<edge> graph[90];
vector<pll> direct_dist[90];
ll dist_back[90];
ll dist[90];
ll dist2[90];
vector<info> infos_direct[90];
vector<info> infos_indirect[90];
ll direct_ans[90][90];
ll indirect_ans[90][90];
bool odw[90];
ll cur_best[90];
void direct_back(int v, ll time)
{
rep(i,n) cur_best[i] = -1;
rep(i,n) odw[i] = 0;
cur_best[v] = time;
rep(i,n)
{
pll max_ = {(ll)-1,-1};
rep(j,n) if(!odw[j]) max_ = max(max_,{cur_best[j],j});
if(max_.ff == -1) break;
odw[max_.ss] = 1;
forall(it,graph[max_.ss]) cur_best[it.v] = max(cur_best[it.v],min(max_.ff-it.L,it.time));
}
rep(i,n) dist_back[i] = cur_best[i];
}
void direct(int v, ll time)
{
rep(i,n) cur_best[i] = 1e18;
rep(i,n) odw[i] = 0;
cur_best[v] = time;
rep(i,n)
{
pll min_ = {(ll)1e18,-1};
rep(j,n) if(!odw[j]) min_ = min(min_,{cur_best[j],j});
if(min_.ff == 1e18) break;
odw[min_.ss] = 1;
forall(it,graph[min_.ss]) if(min_.ff <= it.time) cur_best[it.v] = min(cur_best[it.v],min_.ff+it.L);
}
rep(i,n) dist[i] = cur_best[i];
}
void indirect(int v)
{
rep(i,n) cur_best[i] = 1e18;
rep(i,n) odw[i] = 0;
cur_best[v] = 0;
rep(i,n)
{
pll min_ = {(ll)1e18,-1};
rep(j,n) if(!odw[j]) min_ = min(min_,{cur_best[j],j});
if(min_.ff == 1e18) break;
odw[min_.ss] = 1;
forall(it,graph[min_.ss])
{
if(min_.ff%S <= it.time) cur_best[it.v] = min(cur_best[it.v],min_.ff+it.L);
else cur_best[it.v] = min(cur_best[it.v],min_.ff+S-(min_.ff%S)+it.L);
}
}
rep(i,n) dist2[i] = cur_best[i];
}
vl calculate_necessary_time(int N, int m, ll S2, int q, vi A, vi B, vl L, vl C, vi U, vi V, vl T)
{
S = S2;
n = N;
query_ans.resize(q,1e18);
rep(i,m)
{
graph[A[i]].pb({B[i],L[i],C[i]-L[i]});
graph[B[i]].pb({A[i],L[i],C[i]-L[i]});
}
rep(i,m)
{
rep(d,2)
{
direct_back(A[i],C[i]-L[i]);
direct(B[i],C[i]);
indirect(B[i]);
rep(beg,n)
{
if(dist_back[beg] == -1) continue;
info add;
info add2;
add.time = dist_back[beg];
add2.time = dist_back[beg];
rep(dest,n)
{
if(dist[dest] != 1e18) add.dists[dest] = dist[dest]-dist_back[beg];
if(dist2[dest] != 1e18) add2.dists[dest] = dist2[dest]+S;
}
infos_direct[beg].pb(add);
infos_indirect[beg].pb(add2);
}
swap(A[i],B[i]);
}
}
rep(i,n)
{
sort(all(infos_direct[i]));
sort(all(infos_indirect[i]));
rep(j,n)
{
indirect_ans[i][j] = 1e18;
direct_ans[i][j] = 1e18;
}
}
vector<query> queries;
rep(i,q)
{
queries.pb({T[i],0,U[i],V[i],i});
queries.pb({0,S-T[i],U[i],V[i],i});
}
sort(all(queries));
forall(it,queries)
{
while(!infos_direct[it.a].empty() && infos_direct[it.a].back().time >= it.time)
{
rep(i,n) direct_ans[it.a][i] = min(direct_ans[it.a][i],infos_direct[it.a].back().dists[i]);
infos_direct[it.a].pop_back();
}
while(!infos_indirect[it.a].empty() && infos_indirect[it.a].back().time >= it.time)
{
rep(i,n) indirect_ans[it.a][i] = min(indirect_ans[it.a][i],infos_indirect[it.a].back().dists[i]);
infos_indirect[it.a].pop_back();
}
query_ans[it.ind] = min({query_ans[it.ind],direct_ans[it.a][it.b]+it.add,indirect_ans[it.a][it.b]+it.add-it.time});
}
return query_ans;
}
