P9734 [JOISC 2021] 逃走経路 (Escape Route) (Day2)

在洛谷上提交本题**不是**交互题，请注意提交方式。 本题测试数据很大，评测可能需要加载 1-2 分钟。 [英文题面](https://www2.ioi-jp.org/camp/2021/2021-sp-tasks/day2/escape_route-en.pdf)。

IOI 王国使用 Byou（秒）作为时间单位，将一天划分成 $S$ Byou，分别称为时刻 $0,1,\dotsc,S-1$。 IOI 王国中有 $N$ 个城市和 $M$ 条双向道路，均从 $0$ 开始标号。保证任两个城市之间均连通。第 $i$ 条道路连接城市 $A_i$ 和 $B_i$，需要恰好 $L_i$ Byou 通过。每天的时刻 $C_i$ 后，第 $i$ 条道路将开始进行检查，直到当天结束。 JOI 组织是一个活跃在 IOI 王国中的秘密团体。出于其保密性，成员不能在道路上受到检查。如果其成员想要通过道路 $i$，最晚要在时刻 $C_i-L_i$ 到达这条路的一端。道路的检查不会影响两端的城市。 现在有 $Q$ 名 JOI 组织的成员，从 $0$ 开始标号。第 $j$ 名成员在某天的时刻 $T_j$，要从城市 $U_j$ 出发去城市 $V_j$。成员可以在任意城市内停留任意长的时间。注意这名成员可能会在路上花费一天以上。 请计算每名成员花费的最短时间，精确到 Byou.

第一行四个正整数 $N,M,S,Q$。 接下来 $M$ 行，第 $i$ 行四个正整数表示 $A_{i-1},B_{i-1},L_{i-1},C_{i-1}$。 接下来 $Q$ 行，第 $i$ 行三个正整数表示 $U_{i-1},V_{i-1},T_{i-1}$。

输出共 $Q$ 行，第 $i$ 行表示第 $i-1$ 名成员旅行所需的最短时间。

对于 $100\%$ 的数据，保证： - $2 \leq N \leq 90$。 - $N-1 \leq M \leq \dfrac{N(N-1)}{2}$。 - $2 \leq S \leq 10^{15}$。 - $1 \leq Q \leq 3 \times 10^6$。 - $0 \leq A_i,B_i \leq N-1$。 - $A_i \neq B_i$。 - $\forall i,j \in [0,M-1]$，若 $i \neq j$，则有 $(A_i,B_i) \neq (A_j,B_j),(A_i,B_i) \neq (B_j,A_j)$。 - $1 \leq L_i \leq C_i < S$。 - 从任意城市出发走过一些边后，可以到达任意其他城市。 - $0\leq U_j,V_j \leq N-1$。 - $U_j \neq V_j$。 - $0 \leq T_j < S$。 有 $5 \%$ 的分数，满足 $N \leq 40,Q \leq 1000$。 另有 $20 \%$ 的分数，满足 $N \leq 40,U_j=0$ 另有 $10 \%$ 的分数，满足 $N \leq 40$。 另有 $35 \%$ 的分数，满足 $N \leq 60$。 **建议使用较快的 IO 方式。**