CF730C.Bulmart

A new trade empire is rising in Berland. Bulmart, an emerging trade giant, decided to dominate the market of ... shovels! And now almost every city in Berland has a Bulmart store, and some cities even have several of them! The only problem is, at the moment sales are ... let's say a little below estimates. Some people even say that shovels retail market is too small for such a big company to make a profit. But the company management believes in the future of that market and seeks new ways to increase income.

There are n cities in Berland connected with m bi-directional roads. All roads have equal lengths. It can happen that it is impossible to reach a city from another city using only roads. There is no road which connects a city to itself. Any pair of cities can be connected by at most one road.

There are w Bulmart stores in Berland. Each of them is described by three numbers:

• c__i — the number of city where the i-th store is located (a city can have no stores at all or have several of them),
• k__i — the number of shovels in the i-th store,
• p__i — the price of a single shovel in the i-th store (in burles).

The latest idea of the Bulmart management is to create a program which will help customers get shovels as fast as possible for affordable budget. Formally, the program has to find the minimum amount of time needed to deliver r__j shovels to the customer in the city g__j for the total cost of no more than a__j burles. The delivery time between any two adjacent cities is equal to 1. If shovels are delivered from several cities, the delivery time is equal to the arrival time of the last package. The delivery itself is free of charge.

The program needs to find answers to q such queries. Each query has to be processed independently from others, i.e. a query does not change number of shovels in stores for the next queries.

一个崭新的贸易帝国正在贝尔兰崛起。新兴贸易巨头布尔玛特（Bulmart）决心主导……铲子市场！如今，贝尔兰几乎每座城市都拥有一家布尔玛特门店，部分城市甚至拥有多家门店！唯一的问题是，目前的销量……姑且说，略低于预期。甚至有人指出，铲子零售市场对于如此庞大的公司而言规模过小，难以实现盈利。但公司管理层坚信该市场的未来，并积极探索增加收入的新途径。

贝尔兰共有 $n$ 座城市，由 $m$ 条双向道路连接。所有道路长度相等。可能存在某些城市之间仅通过道路无法相互到达的情况。不存在连接某城市与其自身的道路。任意两座城市之间至多由一条道路直接相连。

贝尔兰共有 $w$ 家布尔玛特门店。每家门店由三个整数描述：

• $c_i$ —— 第 $i$ 家门店所在的城市编号（一座城市可能没有任何门店，也可能拥有多家门店），
• $k_i$ —— 第 $i$ 家门店所拥有的铲子数量，
• $p_i$ —— 第 $i$ 家门店中单把铲子的价格（单位：布尔勒斯，burles）。

布尔玛特管理层最新的构想是开发一款程序，帮助顾客以尽可能快的速度、在可承受的预算内获取铲子。形式化地，该程序需对每个查询求出：为城市 $g_j$ 的顾客配送 $r_j$ 把铲子所需的最短时间，且总花费不超过 $a_j$ 布尔勒斯。任意两个相邻城市之间的配送时间为 $1$。若铲子从多个城市发出，则总配送时间等于最后一个包裹抵达的时间。配送本身免费。

该程序需处理 $q$ 个此类查询。每个查询均需独立处理（即前一查询不会影响后续查询中各门店的铲子库存数量）。

The first line contains two integers n, m (1 ≤ n ≤ 5000, 0 ≤ m ≤ min(5000, n·(n - 1) / 2)). Each of the next m lines contains two integers x__e and y__e, meaning that the e-th road connects cities x__e and y__e (1 ≤ x__e, y__e ≤ n).

The next line contains a single integer w (1 ≤ w ≤ 5000) — the total number of Bulmart stores in Berland. Each of the next w lines contains three integers describing the i-th store: c__i, k__i, p__i (1 ≤ c__i ≤ n, 1 ≤ k__i, p__i ≤ 2·105).

The next line contains a single integer q (1 ≤ q ≤ 1000) — the number of queries. Each of the next q lines contains three integers describing the j-th query: g__j, r__j and a__j (1 ≤ g__j ≤ n, 1 ≤ r__j, a__j ≤ 109)

第一行包含两个整数 $n$、$m$（$1 ≤ n ≤ 5000$，$0 ≤ m ≤ \min(5000, n·(n - 1) / 2)$）。接下来的 $m$ 行每行包含两个整数 $x_e$ 和 $y_e$，表示第 $e$ 条道路连接城市 $x_e$ 和 $y_e$（$1 ≤ x_e, y_e ≤ n$）。

接下来一行包含一个整数 $w$（$1 ≤ w ≤ 5000$）—— Berland 国内 Bulmart 商店的总数。接下来的 $w$ 行每行包含三个整数，描述第 $i$ 家商店：$c_i$、$k_i$、$p_i$（$1 ≤ c_i ≤ n$，$1 ≤ k_i, p_i ≤ 2·10^5$）。

接下来一行包含一个整数 $q$（$1 ≤ q ≤ 1000$）—— 查询的数量。接下来的 $q$ 行每行包含三个整数，描述第 $j$ 个查询：$g_j$、$r_j$ 和 $a_j$（$1 ≤ g_j ≤ n$，$1 ≤ r_j, a_j ≤ 10^9$）。

Output q lines. On the j-th line, print an answer for the j-th query — the minimum amount of time needed to deliver r__j shovels to the customer in city g__j spending no more than a__j burles. Print -1 if there is no solution for the j-th query.

输出 q 行。在第 j 行中，输出第 j 个查询的答案——即在花费不超过 a__j burles 的前提下，将 r__j 把铁锹送达城市 g__j 的客户所需的最短时间。若第 j 个查询无解，则输出 -1。