A10598 | Bulmart

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·10^{5}$ ).

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}<=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.

无