一个新的贸易帝国正在贝尔兰崛起。 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