P4764 [CERC2014] Pork barrel

赢得选举比你预期的要简单：只需承诺最终建立一个高质量的全国性道路基础设施，当然不能让预算瘫痪……然而你的快乐并没有持续多久：似乎市民们找到了一个方法，实际上让你对你的承诺负责！ 在你的国家有 $n$ 个主要城市。交通部准备了一份详细的地图，列出了 $m$ 条可能的高速公路连接及其成本。质量保证委员会不会让你修建成本低于 $l$ 的高速公路，而国家支出监管委员会不会让你修建成本高于 $h$ 的高速公路。为了声称拥有一个“全国性”的网络，你必须在这两个限制内尽可能多地连接（可能是间接地）城市对。你必须找到最便宜的方法来做到这一点，而且必须快速找到！在所有满足限制并连接最多城市对的网络中，计算出最便宜的一个的成本。 更糟糕的是，这两个委员会都受到你愤怒的竞争对手的强烈影响：每次你公布你精心准备的计划时，他们立即改变他们的裁决 $l$ 和 $h$，你被迫从头开始。

输入的第一行包含测试用例的数量 $T$。接下来的描述是测试用例的内容： 每个测试用例的第一行包含整数 $n$ 和 $m(1 \le n \le 1000, 0 \le m \le 100 000)$——国家中的城市数量和可能的直接连接数量。 接下来的 $m$ 行中的每一行包含三个整数 $x, y, w (1 \le x eq y \le n, 1 \le w \le 1 000 000)$，表示城市 $x$ 和 $y$ 可以通过成本为 $w$ 的双向高速公路连接。可能有多种方式连接单对城市。 接下来的行包含一个整数 $q(1 \le q \le 1 000 000)$——委员会的裁决数量。接下来的 $q$ 行中的第一行直接给出初始裁决 $l_1, h_1$。其余的裁决是编码的。对于 $j > 1$ 的行中的数字是 $l_j + c_{j -1}$ 和 $h_j + c_{j-1}$，其中 $l_j$ 和 $h_j$ 是实际的裁决，$c_{j-1}$ 是前一个裁决 $l_{j-1}$ 和 $h_{j-1}$ 的正确答案。 所有裁决满足 $1 \le l_j \le h_j \le 1 000 000$。

对于每个测试用例，输出 $q$ 行，每个裁决一行。在第 $j$ 行中，输出符合委员会限制并创建最大数量连接城市对的高速公路网络的最小成本 $c_j$。

题面翻译由 ChatGPT-4o 提供。