← 返回题目列表

Codeforces · 730/C

C. 布尔玛特

中文机器翻译题面 查看原题

一个新的贸易帝国正在贝尔兰崛起。 Bulmart,一个新兴的贸易巨头,决定主导……铲子市场!而现在伯兰几乎每个城市都有Bulmart专卖店,有的城市甚至有好几家!唯一的问题是,目前的销售额……可以说略低于估计。甚至有人说,铲子零售市场太小,这么大的公司盈利不了。但公司管理层相信该市场的未来,并寻求新的方法来增加收入。

Berland 有 n 个城市,有 m 条双向道路相连。所有道路的长度都相等。可能会出现仅通过道路无法从另一个城市到达另一个城市的情况。没有一条道路可以将一座城市与其本身连接起来。任何一对城市最多可以通过一条道路连接。

Berland 有 w Bulmart 商店。每个都由三个数字描述:

- ci — 第 i 个商店所在的城市数量(一个城市可以根本没有商店或有多个商店),
- ki — 第 i 个商店中的铲子数量,
- pi — 第 i 个商店中单个铲子的价格(以布尔为单位)。

Bulmart 管理层的最新想法是创建一个计划,帮助客户以负担得起的预算尽快获得铲子。形式上,该程序必须找到向 gj 城市的客户交付 rj 铲子所需的最短时间,且总成本不超过 aj burles。任意两个相邻城市之间的配送时间等于1。如果从多个城市配送铲子,则配送时间等于最后一个包裹的到达时间。送货本身是免费的。

程序需要找到 q 个此类查询的答案。每个查询必须独立于其他查询进行处理,即查询不会更改存储中用于下一个查询的铲子数量。

输入

第一行包含两个整数 n、m (1 ≤ n ≤ 5000, 0 ≤ m ≤ min(5000, n·(n - 1) / 2))。接下来的 m 行每行包含两个整数 xe 和 ye,意味着第 e 条路连接城市 xe 和 ye(1 ≤ xe,ye ≤ n)。

下一行包含一个整数 w (1 ≤ w ≤ 5000) — Berland 的 Bulmart 商店总数。接下来的 w 行中的每一行都包含描述第 i 个存储的三个整数:ci, ki, pi (1 ≤ ci ≤ n, 1 ≤ ki, pi ≤ 2·105)。

下一行包含一个整数 q (1 ≤ q ≤ 1000) — 查询数。接下来的 q 行中的每一行都包含描述第 j 个查询的三个整数:gj、rj 和 aj (1 ≤ gj ≤ n, 1 ≤ rj, aj ≤ 109)

输出

输出 q 行。在第 j 行,打印第 j 个查询的答案 — 将 rj 铲子交付给 gj 城市的客户所需的最短时间,花费不超过 aj burles。如果第 j 个查询没有解决方案,则打印 -1。

示例

输入 #1

6 4
4 2
5 4
1 2
3 2
2
4 1 2
3 2 3
6
1 2 6
2 3 7
3 1 2
4 3 8
5 2 5
6 1 10

输出 #1

2
-1
2
2
3
-1