#include "escape_route.h"
#include <cstring>
using namespace std;
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
const int N = 90, M = N * (N - 1) / 2, Q = 3000000;
const long long INF = 0x3f3f3f3f3f3f3f3f;
typedef vector<int> vi;
typedef vector<long long> vl;
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ii[Q], jj[Q], hh[Q]; long long rr[Q];
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = ii[hh[j]] != ii[h] ? ii[hh[j]] - ii[h] : (rr[hh[j]] == rr[h] ? 0 : rr[hh[j]] < rr[h] ? -1 : 1);
if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}
long long ww[N][N], cc[N][N], dd1[N][N], dd2[N][N], dd[N]; int pp[N], qu[N]; char visited[N], update[N];
vl calculate_necessary_time(int n, int m, long long md, int q, vi uu_, vi vv_, vl ww_, vl cc_, vi ii_, vi jj_, vl rr_) {
for (int i = 0; i < n; i++)
memset(ww[i], 0x3f, n * sizeof *ww[i]);
for (int h = 0; h < m; h++) {
int u = uu_[h], v = vv_[h];
ww[u][v] = ww[v][u] = ww_[h], cc[u][v] = cc[v][u] = cc_[h] - ww_[h];
}
for (int t = 0; t < n; t++) {
memset(dd1[t], -1, n * sizeof *dd1[t]), dd1[t][t] = md;
memset(visited, 0, n * sizeof *visited);
for (int h = 0; h < n; h++) {
int j, j_ = -1;
for (j = 0; j < n; j++)
if (!visited[j] && (j_ == -1 || dd1[t][j_] < dd1[t][j]))
j_ = j;
j = j_;
visited[j] = 1;
long long d = dd1[t][j];
for (int i = 0; i < n; i++)
if (!visited[i] && ww[i][j] != INF)
dd1[t][i] = max(dd1[t][i], min(d - ww[i][j], cc[i][j]));
}
}
for (int s = 0; s < n; s++) {
memset(dd2[s], 0x3f, n * sizeof *dd2[s]), dd2[s][s] = 0;
memset(visited, 0, n * sizeof *visited);
for (int h = 0; h < n; h++) {
int i, i_ = -1;
for (i = 0; i < n; i++)
if (!visited[i] && (i_ == -1 || dd2[s][i_] > dd2[s][i]))
i_ = i;
i = i_;
visited[i] = 1;
long long d = dd2[s][i];
for (int j = 0; j < n; j++)
if (!visited[j] && ww[i][j] != INF)
dd2[s][j] = min(dd2[s][j], (d % md <= cc[i][j] ? d : (d + md - 1) / md * md) + ww[i][j]);
}
}
for (int h = 0; h < q; h++)
ii[h] = ii_[h], jj[h] = jj_[h], rr[h] = rr_[h];
for (int h = 0; h < q; h++)
hh[h] = h;
sort(hh, 0, q);
vl ans(q);
for (int h = 0, h_; h < q; h = h_) {
int s = ii[hh[h]];
h_ = h;
while (h_ < q && ii[hh[h_]] == s)
h_++;
for (int i = 0; i < n; i++)
qu[i] = i;
for (int h1 = h; h1 < h_; h1++) {
int h1_ = hh[h1], t = jj[h1_];
long long r = rr[h1_];
int upd = h1 == h;
for (int i = 0; i < n; i++)
if (pp[i] != -1 && dd[pp[i]] > cc[pp[i]][i] - r) {
upd = 1;
break;
}
if (upd) {
for (int g = 0; g < n; g++) {
int i = qu[g];
update[i] = h1 == h || pp[i] != -1 && (update[pp[i]] || dd[pp[i]] > cc[pp[i]][i] - r);
}
int m = 0;
for (int g = 0; g < n; g++) {
int i = qu[g], tmp;
if (!update[i])
tmp = qu[g], qu[g] = qu[m], qu[m] = tmp, m++;
else
dd[i] = INF, pp[i] = -1;
}
dd[s] = 0;
for (int g = 0; g < m; g++) {
int i = qu[g];
long long d = dd[i], d_;
for (int g_ = m; g_ < n; g_++) {
int j = qu[g_];
if (ww[i][j] != INF && d <= cc[i][j] - r && dd[j] > (d_ = d + ww[i][j]))
dd[j] = d_, pp[j] = i;
}
}
for (int g = m; g < n; g++) {
int tmp;
for (int g_ = g + 1; g_ < n; g_++)
if (dd[qu[g]] > dd[qu[g_]])
tmp = qu[g], qu[g] = qu[g_], qu[g_] = tmp;
int i = qu[g];
long long d = dd[i], d_;
for (int g_ = m + 1; g_ < n; g_++) {
int j = qu[g_];
if (ww[i][j] != INF && d <= cc[i][j] - r && dd[j] > (d_ = d + ww[i][j]))
dd[j] = d_, pp[j] = i;
}
}
}
ans[h1_] = dd[t];
for (int k = 0; k < n; k++)
if (dd1[k][s] >= r && dd2[k][t] != INF)
ans[h1_] = min(ans[h1_], md - r + dd2[k][t]);
}
}
return ans;
}
