1605_最小瓶颈路加强版

给定一个 n 个点 m 条边的无向连通图，编号为 1 到 n ，没有自环，可能有重边，每一条边有一个正权值 w 。

给出 q 个询问，每次给出两个不同的点 u 和 v ，求一条从 u 到 v 的路径上边权的最大值最小是多少。

输入第一行两个整数 n , m。

接下来 m 行，每行三个整数 a_i, b_i, w_i ( a_i ≠ b_i )，表示一条边 (a_i, b_i)，边权为 w_i 。

接下来一行一个整数 q，表示询问数量。

接下来一行四个整数 A, B, C, P，表示询问的生成方式。

由于本题数据规模较大，直接输入输出会占用比计算多数倍的时间，因此对询问的输入输出进行了压缩。

输入压缩方法是：读入4个整数 A, B, C, P，每次询问调用以下函数生成 u 和 v：

int A, B, C, P;

inline int rnd( ) { return A=(A*B+C)%P; }

每次询问时的调用方法为：

u = rnd()%n+1, v = rnd()%n+1;

若u和v相等则答案为0。

数据保证 0 ≤ A < P ,  0 ≤ C < P ,   P(B+1) < 2³¹−1

输出共一行一个整数，表示所有询问的答案之和模 1000000007 的值。

由于本题数据规模较大，直接输入输出会占用比计算多数倍的时间，因此对询问的输入输出进行了压缩。

输出压缩方法是：输出所有询问的答案之和模 1000000007 的值。

5 7
1 2 8
2 3 9
3 1 2
3 4 7
1 4 4
3 5 6
1 4 9
10
233 17 66666 19260817

32

对于所有数据，n ≤ 70000，m ≤ 100000，q ≤ 10⁷ 。