CF730C Bulmart

Berland 的一股新的商业力量正在崛起。作为铲子领域的新兴贸易巨头，Bulmart 准备主宰这一市场！如今，几乎每个 Berland 城市都有 Bulmart 商店，有些城市甚至有多家。唯一的问题是，当前的销售额……远低于预期。一些人认为，铲子零售市场的规模过小，大公司难以从中获益。但公司管理层对市场的未来充满信心，正在寻找提升收入的新方法。 Berland 有 $ n $ 座城市，通过 $ m $ 条双向道路相连。所有道路的长度都相同。可能出现某些城市之间无法通过道路直接到达的情况。没有一条道路连接同一个城市，任意两个城市之间最多只有一条道路。 Berland 有 $ w $ 家 Bulmart 商店。每家商店信息包括： - $ c_{i} $ — 第 $ i $ 家商店所在城市的编号（一个城市可能没有商店，也可能有多个）， - $ k_{i} $ — 第 $ i $ 家商店的铲子数量， - $ p_{i} $ — 第 $ i $ 家商店中每把铲子的价格（以 burles 为单位）。 Bulmart 管理层最新的想法是开发一个程序，帮助顾客在预算内快捷地购买到铲子。具体来说，该程序需要找到在不超过 $ a_{j} $ burles 的总预算下，将 $ r_{j} $ 把铲子运送到城市 $ g_{j} $ 的顾客的手中所需的最短时间。任意两个相邻城市之间的运送时间是 $ 1 $。如果铲子是从多个城市运送来的，运送时间即为最后一批货物到达的时间。运送过程是免费的。 程序需要处理 $ q $ 个独立的查询。每个查询独立计算，一次查询不会影响后续查询中的商店库存。

第一行包含两个整数 $ n $ 和 $ m $ ，表示 Berland 有 $ n $ 座城市，和 $ m $ 条道路（$ 1 \le n \le 5000 $ ，$ 0 \le m \le \min(5000, n \cdot (n-1) / 2) $）。接下来的 $ m $ 行每行包含两个整数 $ x_{e} $ 和 $ y_{e} $，表示第 $ e $ 条道路连接城市 $ x_{e} $ 和 $ y_{e} $ （$ 1 \le x_{e}, y_{e} \le n $）。 随后一行包含一个整数 $ w $ （$ 1 \le w \le 5000 $），表示 Bulmart 的商店总数。接下来的 $ w $ 行每行包含三个整数，分别描述第 $ i $ 家商店的信息：$ c_{i}, k_{i}, p_{i} $ （$ 1 \le c_{i} \le n $, $ 1 \le k_{i}, p_{i} \le 2 \cdot 10^{5} $）。 接下来的第二部分输入是查询部分，首先是一个整数 $ q $ （$ 1 \le q \le 1000 $），表示查询的数量。接着的 $ q $ 行，每行包含三个整数，描述第 $ j $ 个查询：$ g_{j}, r_{j} $ 和 $ a_{j} $ （$ 1 \le g_{j} \le n $, $ 1 \le r_{j}, a_{j} \le 10^{9} $）。

输出共有 $ q $ 行。每行输出第 $ j $ 个查询的答案：并在总费用不超过 $ a_{j} $ burles 的情况下，将 $ r_{j} $ 把铲子运送到城市 $ g_{j} $ 所需的最短时间。如果无法满足条件，则输出 -1。 **本翻译由 AI 自动生成**