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: 

  * ci — the number of city where the i-th store is located (a city can have no stores at all or have several of them), 
  * ki — the number of shovels in the i-th store, 
  * pi — 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 rj shovels to the customer in the city gj for the total cost of no more than aj 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.

Input

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 xe and ye, meaning that the e-th road connects cities xe and ye (1 ≤ xe, ye ≤ 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: ci, ki, pi (1 ≤ ci ≤ n, 1 ≤ ki, pi ≤ 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: gj, rj and aj (1 ≤ gj ≤ n, 1 ≤ rj, aj ≤ 109)

Output

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

Example

Input

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


Output

2
-1
2
2
3
-1
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * #
 * 
 * @author pttrung
 */
public class C_NEERC_2016 {

	public static long MOD = 1000000007;

	public static void main(String[] args) throws FileNotFoundException {
		// PrintWriter out = new PrintWriter(new FileOutputStream(new File(
		// "output.txt")));
		PrintWriter out = new PrintWriter(System.out);
		Scanner in = new Scanner();
		int n = in.nextInt();
		int m = in.nextInt();
		ArrayList<Integer>[] map = new ArrayList[n];
		ArrayList<Point>[] store = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			map[i] = new ArrayList();
			store[i] = new ArrayList();
		}
		for (int i = 0; i < m; i++) {
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			map[a].add(b);
			map[b].add(a);
		}
		int w = in.nextInt();
		for (int i = 0; i < w; i++) {
			int c = in.nextInt() - 1;
			int a = in.nextInt();
			int b = in.nextInt();
			store[c].add(new Point(a, b));

		}
		for (int i = 0; i < n; i++) {
			Collections.sort(store[i], new Comparator<Point>() {

				@Override
				public int compare(Point o1, Point o2) {
					// TODO Auto-generated method stub
					return Integer.compare(o1.y, o2.y);
				}
			});
		}
		int q = in.nextInt();
		int[] tmp = new int[n];

		int[] dist = new int[n];
		int[] check = new int[n];
		Arrays.fill(check, -1);
		for (int i = 0; i < q; i++) {
			int g = in.nextInt() - 1;
			int k = in.nextInt();
			int a = in.nextInt();
			int result = -1;
			int st = 0;
			int ed = 0;

			int total = 0;
			long cost = 0;
			check[g] = i;
			dist[g] = 0;
			tmp[ed++] = g;
			PriorityQueue<Point> pq = new PriorityQueue<>();
			for (Point p : store[g]) {
				if(total >= k && pq.peek().y <= p.y){
					break;
				}
				pq.add(new Point(p.x, p.y));
				total += p.x;
				cost += (long) p.x * (long) p.y;
			}
			while (total > k) {
				Point p = pq.poll();
				if (total - p.x >= k) {
					cost -= (long) p.x * (long) p.y;
					total -= p.x;
				} else {
					int max = total - k;
					p.x -= max;
					cost -= (long) max * (long) p.y;
					total -= max;
					pq.add(p);
				}
			}
			if (cost <= a && total == k) {

				result = 0;

			}
			while (st < ed && (total < k || cost > a)) {
				int node = tmp[st++];
				for (int j : map[node]) {
					if (check[j] != i) {
						check[j] = i;
						dist[j] = 1 + dist[node];
						for (Point p : store[j]) {
							if(total >= k && pq.peek().y <= p.y){
								break;
							}
							pq.add(new Point(p.x, p.y));
							total += p.x;
							cost += (long) p.x * (long) p.y;
						}
						while (total > k) {
							Point p = pq.poll();
							if (total - p.x >= k) {
								cost -= (long) p.x * (long) p.y;
								total -= p.x;
							} else {
								int max = total - k;
								p.x -= max;
								cost -= (long) max * (long) p.y;
								total -= max;
								pq.add(p);
							}
						}

						if (cost <= a && total == k) {

							result = dist[j];
							break;
						}
						tmp[ed++] = j;
					}

				}
			}

			out.println(result);

		}

		out.close();
	}

	public static int[] KMP(String val) {
		int i = 0;
		int j = -1;
		int[] result = new int[val.length() + 1];
		result[0] = -1;
		while (i < val.length()) {
			while (j >= 0 && val.charAt(j) != val.charAt(i)) {
				j = result[j];
			}
			j++;
			i++;
			result[i] = j;
		}
		return result;

	}

	public static boolean nextPer(int[] data) {
		int i = data.length - 1;
		while (i > 0 && data[i] < data[i - 1]) {
			i--;
		}
		if (i == 0) {
			return false;
		}
		int j = data.length - 1;
		while (data[j] < data[i - 1]) {
			j--;
		}
		int temp = data[i - 1];
		data[i - 1] = data[j];
		data[j] = temp;
		Arrays.sort(data, i, data.length);
		return true;
	}

	public static int digit(long n) {
		int result = 0;
		while (n > 0) {
			n /= 10;
			result++;
		}
		return result;
	}

	public static double dist(long a, long b, long x, long y) {
		double val = (b - a) * (b - a) + (x - y) * (x - y);
		val = Math.sqrt(val);
		double other = x * x + a * a;
		other = Math.sqrt(other);
		return val + other;

	}

	public static class Point implements Comparable<Point> {

		int x, y;

		public Point(int start, int end) {
			this.x = start;
			this.y = end;
		}

		@Override
		public int hashCode() {
			int hash = 5;
			hash = 47 * hash + this.x;
			hash = 47 * hash + this.y;
			return hash;
		}

		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}

		@Override
		public boolean equals(Object obj) {
			if (obj == null) {
				return false;
			}
			if (getClass() != obj.getClass()) {
				return false;
			}
			final Point other = (Point) obj;
			if (this.x != other.x) {
				return false;
			}
			if (this.y != other.y) {
				return false;
			}
			return true;
		}

		@Override
		public int compareTo(Point o) {
			return Integer.compare(o.y, y);
		}
	}

	public static class FT {

		long[] data;

		FT(int n) {
			data = new long[n];
		}

		public void update(int index, long value) {
			while (index < data.length) {
				data[index] += value;
				index += (index & (-index));
			}
		}

		public long get(int index) {
			long result = 0;
			while (index > 0) {
				result += data[index];
				index -= (index & (-index));
			}
			return result;

		}
	}

	public static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}

	public static long pow(long a, long b) {
		if (b == 0) {
			return 1;
		}
		if (b == 1) {
			return a;
		}
		long val = pow(a, b / 2);
		if (b % 2 == 0) {
			return val * val % MOD;
		} else {
			return val * (val * a % MOD) % MOD;

		}
	}

	static class Scanner {

		BufferedReader br;
		StringTokenizer st;

		public Scanner() throws FileNotFoundException {
			// System.setOut(new PrintStream(new
			// BufferedOutputStream(System.out), true));
			br = new BufferedReader(new InputStreamReader(System.in));
			// br = new BufferedReader(new InputStreamReader(new
			// FileInputStream(new File("input.txt"))));
		}

		public String next() {

			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					throw new RuntimeException();
				}
			}
			return st.nextToken();
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String nextLine() {
			st = null;
			try {
				return br.readLine();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}

		public boolean endLine() {
			try {
				String next = br.readLine();
				while (next != null && next.trim().isEmpty()) {
					next = br.readLine();
				}
				if (next == null) {
					return true;
				}
				st = new StringTokenizer(next);
				return st.hasMoreTokens();
			} catch (Exception e) {
				throw new RuntimeException();
			}
		}
	}
}
