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.*;
import java.util.*;
import java.util.function.Function;

public class C_special4
{
    public static final Random RANDOM = new Random(System.currentTimeMillis());
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer stringTokenizer = null;
    private static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    private static String next() throws IOException
    {
        while ((stringTokenizer == null) || (!stringTokenizer.hasMoreTokens()))
        {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        }
        return stringTokenizer.nextToken();
    }

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

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

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

    public static String nextLine() throws IOException
    {
        return bufferedReader.readLine();
    }

    public static void close()
    {
        out.close();
    }

    public static final long[] POWER2 = generatePOWER2();

    static class Array<Type>
    {
        private Object[] array;

        public Array(int size)
        {
            this.array = new Object[size];
        }

        public Array(int size, Type element)
        {
            this(size);
            Arrays.fill(this.array, element);
        }

        public Array(Array<Type> array, Type element)
        {
            this(array.size() + 1);
            for (int index = 0; index < array.size(); index++)
            {
                set(index, array.get(index));
            }
            set(size() - 1, element);
        }

        public Array(List<Type> list)
        {
            this(list.size());
            int index = 0;
            for (Type element: list)
            {
                set(index, element);
                index += 1;
            }
        }

        public Type get(int index)
        {
            return (Type)this.array[index];
        }
        public Array set(int index, Type value)
        {
            this.array[index] = value;
            return this;
        }

        public int size()
        {
            return this.array.length;
        }

        public List<Type> toList()
        {
            List<Type> result = new ArrayList<Type>();
            for (int index = 0; index < array.length; index++)
            {
                result.add(get(index));
            }
            return result;
        }
    }

    interface BiFunctionResult<Type0, Type1, TypeResult>
    {
        TypeResult apply(Type0 x0, Type1 x1, TypeResult x2);
    }

    static abstract class Edge<TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>>
    {
        public final TypeVertex vertex0;
        public final TypeVertex vertex1;

        public Edge(TypeVertex vertex0, TypeVertex vertex1, boolean bidirectional)
        {
            this.vertex0 = vertex0;
            this.vertex1 = vertex1;
            this.vertex0.edges.put(vertex1, getThis());
            if (bidirectional)
            {
                this.vertex1.edges.put(vertex0, getThis());
            }
        }

        private TypeVertex other(Vertex<TypeVertex, TypeEdge> vertex)
        {
            TypeVertex result;
            if (vertex0 == vertex)
            {
                result = vertex1;
            }
            else
            {
                result = vertex0;
            }
            return result;
        }

        public TypeVertex from(Vertex<TypeVertex, TypeEdge> to)
        {
            return other(to);
        }

        public TypeVertex to(Vertex<TypeVertex, TypeEdge> from)
        {
            return other(from);
        }

        public abstract TypeEdge getThis();
    }

    public static class EdgeDefault<TypeVertex extends Vertex<TypeVertex, EdgeDefault<TypeVertex>>> extends Edge<TypeVertex, EdgeDefault<TypeVertex>>
    {
        public EdgeDefault(TypeVertex vertex0, TypeVertex vertex1, boolean bidirectional)
        {
            super(vertex0, vertex1, bidirectional);
        }

        @Override
        public EdgeDefault<TypeVertex> getThis()
        {
            return this;
        }
    }

    public static class Vertex<TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>> implements Comparable<Vertex<? super TypeVertex, ? super TypeEdge>>
    {
        public final int index;
        public final Map<TypeVertex, TypeEdge> edges;

        public Vertex(int index)
        {
            this.index = index;
            this.edges = new TreeMap<>();
        }

        public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult depthFirstSearch(
                BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
                TypeVertex vertex,
                TypeEdge edge,
                TypeResult result,
                boolean[] visited
        )
        {
            if (!visited[vertex.index])
            {
                visited[vertex.index] = true;
                result = function.apply(vertex, edge, result);
                for (Map.Entry<TypeVertex, TypeEdge> entry : vertex.edges.entrySet())
                {
                    TypeVertex vertexNext = entry.getKey();
                    TypeEdge edgeNext = entry.getValue();
                    result = depthFirstSearch(function, vertexNext, edgeNext, result, visited);
                }
            }
            return result;
        }

        public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult depthFirstSearch(
                TypeVertex[] vertices,
                int indexVertexStart,
                BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
                TypeResult result
        )
        {
            boolean[] visited = new boolean[vertices.length];
            return depthFirstSearch(function, vertices[indexVertexStart], null, result, visited);
        }

        public static <TypeVertex extends Vertex<TypeVertex, TypeEdge>, TypeEdge extends Edge<TypeVertex, TypeEdge>, TypeResult> TypeResult breadthFirstSearch(
                TypeVertex[] vertices,
                int indexVertexStart,
                BiFunctionResult<TypeVertex, TypeEdge, TypeResult> function,
                TypeResult result
        )
        {
            Array<Boolean> visited = new Array(vertices.length, Boolean.FALSE);
            LIFO<TypeVertex> verticesNext = new LIFO<>();
            verticesNext.push(vertices[indexVertexStart]);
            LIFO<TypeEdge> edgesNext = new LIFO<>();
            edgesNext.push(null);
            while (!verticesNext.isEmpty())
            {
                TypeVertex vertex = verticesNext.pop();
                TypeEdge edge = edgesNext.pop();
                if (!visited.get(vertex.index))
                {
                    visited.set(vertex.index, true);
                    result = function.apply(vertex, edge, result);
                    for (Map.Entry<TypeVertex, TypeEdge> entry : vertex.edges.entrySet())
                    {
                        TypeVertex vertexNext = entry.getKey();
                        TypeEdge edgeNext = entry.getValue();
                        if (!visited.get(vertexNext.index))
                        {
                            verticesNext.push(vertexNext);
                            edgesNext.push(edgeNext);
                        }
                    }
                }
            }
            return result;
        }

        @Override
        public int compareTo(Vertex<? super TypeVertex, ? super TypeEdge> that)
        {
            return that.index - this.index;
        }
    }

    public static class VertexDefault<TypeEdge extends Edge<VertexDefault<TypeEdge>, TypeEdge>> extends Vertex<VertexDefault<TypeEdge>, TypeEdge>
    {
        public VertexDefault(int index)
        {
            super(index);
        }
    }

    public static class Tuple2<Type0, Type1>
    {
        public final Type0 v0;
        public final Type1 v1;

        public Tuple2(Type0 v0, Type1 v1)
        {
            this.v0 = v0;
            this.v1 = v1;
        }
    }

    public static class Tuple2Comparable<Type0 extends Comparable<? super Type0>, Type1 extends Comparable<? super Type1>> extends Tuple2<Type0, Type1> implements Comparable<Tuple2Comparable<Type0, Type1>>
    {
        public Tuple2Comparable(Type0 v0, Type1 v1)
        {
            super(v0, v1);
        }

        @Override
        public int compareTo(Tuple2Comparable<Type0, Type1> that)
        {
            int result = this.v0.compareTo(that.v0);
            if (result == 0)
            {
                result = this.v1.compareTo(that.v1);
            }
            return result;
        }
    }

    public static class SingleLinkedList<Type>
    {
        public final Type element;
        public SingleLinkedList<Type> next;

        public SingleLinkedList(Type element, SingleLinkedList<Type> next)
        {
            this.element = element;
            this.next = next;
        }

        public void toCollection(Collection<Type> collection)
        {
            if (this.next != null)
            {
                this.next.toCollection(collection);
            }
            collection.add(this.element);
        }
    }

    public static class LIFO<Type>
    {
        public SingleLinkedList<Type> start;
        public SingleLinkedList<Type> end;

        public LIFO()
        {
            this.start = null;
            this.end = null;
        }

        public void push(Type element)
        {
            SingleLinkedList<Type> list = new SingleLinkedList<>(element, null);
            if (this.start == null)
            {
                this.start = list;
                this.end = list;
            }
            else
            {
                this.end.next = list;
                this.end = list;
            }
        }

        public Type pop()
        {
            Type result = this.start.element;
            this.start = this.start.next;
            return result;
        }

        public boolean isEmpty()
        {
            return this.start == null;
        }
    }

    public static class MapCount extends TreeMap<Long, Long>
    {
        private int size;

        public MapCount()
        {
            this.size = 0;
        }

        public MapCount(Comparator<? super Long> comparator)
        {
            super(comparator);
        }

        public long add(Long key, Long delta)
        {
            long result;
            if (delta > 0)
            {
                Long value = get(key);
                if (value == null)
                {
                    value = delta;
                }
                else
                {
                    value += delta;
                }
                put(key, value);
                result = delta;
            }
            else
            {
                result = 0;
            }
            this.size += result;
            return result;
        }

        public long remove(Long key, Long delta)
        {
            long result;
            if (delta > 0)
            {
                Long value = get(key) - delta;
                if (value <= 0)
                {
                    result = delta + value;
                    remove(key);
                }
                else
                {
                    result = delta;
                    put(key, value);
                }
            }
            else
            {
                result = 0;
            }
            this.size -= result;
            return result;
        }

        public int size()
        {
            return this.size;
        }
    }

    public static class MapSet<TypeKey extends Comparable<? super TypeKey>, TypeValue> extends TreeMap<TypeKey, TreeSet<TypeValue>> implements Iterable<TypeValue>
    {
        private int size;
        private Comparator<? super TypeValue> comparatorValue;

        public MapSet()
        {
            this(null);
        }

        public MapSet(Comparator<? super TypeValue> comparatorValue)
        {
            super();
            this.size = 0;
            this.comparatorValue = comparatorValue;
        }

        public TypeValue firstValue()
        {
            TypeValue result;
            Map.Entry<TypeKey, TreeSet<TypeValue>> firstEntry = firstEntry();
            if (firstEntry == null)
            {
                result = null;
            }
            else
            {
                result = firstEntry.getValue().first();
            }
            return result;
        }

        public Iterator<TypeValue> iterator()
        {
            return new Iterator<TypeValue>()
            {
                Iterator<TreeSet<TypeValue>> iteratorValues = values().iterator();
                Iterator<TypeValue> iteratorValue = null;

                @Override
                public boolean hasNext()
                {
                    return iteratorValues.hasNext() || (iteratorValue != null && iteratorValue.hasNext());
                }

                @Override
                public TypeValue next()
                {
                    if (iteratorValue == null || !iteratorValue.hasNext())
                    {
                        iteratorValue = iteratorValues.next().iterator();
                    }
                    return iteratorValue.next();
                }
            };
        }

        public TypeValue lastValue()
        {
            TypeValue result;
            Map.Entry<TypeKey, TreeSet<TypeValue>> lastEntry = lastEntry();
            if (lastEntry == null)
            {
                result = null;
            }
            else
            {
                result = lastEntry.getValue().last();
            }
            return result;
        }

        public boolean add(TypeKey key, TypeValue value)
        {
            TreeSet<TypeValue> set = get(key);
            if (set == null)
            {
                if (comparatorValue == null)
                {
                    set = new TreeSet<>();
                }
                else
                {
                    set = new TreeSet<>(comparatorValue);
                }
                put(key, set);
            }
            boolean result = set.add(value);
            if (result)
            {
                this.size += 1;
            }
            return result;
        }

        public boolean remove(TypeKey key, TypeValue value)
        {
            boolean result;
            TreeSet<TypeValue> set = get(key);
            if (set == null)
            {
                result = false;
            }
            else
            {
                result = set.remove(value);
                if (set.size() == 0)
                {
                    remove(key);
                }
                if (result)
                {
                    this.size -= 1;
                }
            }
            return result;
        }

        @Override
        public int size()
        {
            return this.size;
        }
    }

    public static int binarySearchMinimum(Function<Integer, Boolean> filter, int start, int end)
    {
        int result;
        if (start == end)
        {
            result = end;
        }
        else
        {
            int middle = start + (end - start) / 2;
            if (filter.apply(middle))
            {
                result = binarySearchMinimum(filter, start, middle);
            }
            else
            {
                result = binarySearchMinimum(filter, middle + 1, end);
            }
        }
        return result;
    }

    public static int binarySearchMaximum(Function<Integer, Boolean> filter, int start, int end)
    {
        return -binarySearchMinimum(x -> filter.apply(-x), -end, -start);
    }

    public static long divideCeil(long x, long y)
    {
        return x / y + (x % y == 0 ? 0 : 1);
    }

    public static long faculty(int n)
    {
        long result = 1;
        for (int index = 2; index <= n; index++)
        {
            result *= index;
        }
        return result;
    }

    public static long[] generatePOWER2()
    {
        long[] result = new long[63];
        for (int x = 0; x < result.length; x++)
        {
            result[x] = 1L << x;
        }
        return result;
    }

    public static <T> List<T> permutation(long p, List<T> x)
    {
        List<T> copy = new ArrayList<>();
        for (int index = 0; index < x.size(); index++)
        {
            copy.add(x.get(index));
        }
        List<T> result = new ArrayList<>();
        for (int indexTo = 0; indexTo < x.size(); indexTo++)
        {
            int indexFrom = (int) p % copy.size();
            p = p / copy.size();
            result.add(copy.remove(indexFrom));
        }
        return result;
    }

    public static <Type> void println(Iterator<Type> iterator)
    {
        if (iterator.hasNext())
        {
            out.print(iterator.next());
        }
        while (iterator.hasNext())
        {
            out.print(" " + iterator.next());
        }
        out.println();
    }

    public static <Type> void println(Iterable<Type> iterable)
    {
        println(iterable.iterator());
    }


    public static void main(String[] args)
    {
        try
        {
            solve();
        } catch (IOException exception)
        {
            exception.printStackTrace();
        }
        close();
    }

    static class Store
    {
        public final City city;
        public final int shovelCount;
        public final int price;
        public int distance;

        public Store(City city, int shovelCount, int price)
        {
            this.city = city;
            this.shovelCount = shovelCount;
            this.price = price;
        }

        public String toString()
        {
            return "Store(" + shovelCount + ", " + price + ")";
        }
    }

    static class City extends Vertex<City, EdgeDefault<City>>
    {
        public final List<Store> stores;
        public int distance;

        public City(int index)
        {
            super(index);
            this.stores = new ArrayList<>();
        }

        public String toString()
        {
            return "City(" + this.index + ")";
        }
    }

    public static boolean match(Store[] stores, int distance, int shovelCountMinimum, int priceMaximum)
    {
        Store store;
        for (int index = 0; index < stores.length && 0 < shovelCountMinimum && (store = stores[index]).price <= priceMaximum; index++)
        {
            if (store.distance != -1 && store.distance <= distance)
            {
                int shovels = priceMaximum / store.price;
                if (store.shovelCount < shovels)
                {
                    shovels = store.shovelCount;
                }
                shovelCountMinimum -= shovels;
                priceMaximum -= shovels * store.price;
            }
        }
        return shovelCountMinimum <= 0;
    }

    public static int solve(City[] cities, Store[] stores, int indexCity, int shovelCountMinimum, int priceMaximum)
    {
        for (City city : cities)
        {
            city.distance = -1;
        }
        BiFunctionResult<City, EdgeDefault<City>, Void> function = (city, road, dummy) ->
        {
            city.distance = road == null ? 0 : cities[road.from(city).index].distance + 1;
            return null;
        };
        Vertex.breadthFirstSearch(cities, indexCity, function, null);
        for (Store store : stores)
        {
            store.distance = store.city.distance;
        }
        Function<Integer, Boolean> filter = distance -> match(stores, distance, shovelCountMinimum, priceMaximum);
        int distanceMaximum = binarySearchMinimum(filter, 0, 5000);
        return distanceMaximum == 5000 ? -1 : distanceMaximum;
    }

    public static int[] solve(int n, int m, int[] x, int[] y, int w, int[] c, int[] k, int[] p, int q, int[] g, int[] r, int[] a)
    {
        City[] cities = new City[n];
        for (int index = 0; index < n; index++)
        {
            cities[index] = new City(index);
        }
        for (int index = 0; index < m; index++)
        {
            new EdgeDefault<>(cities[x[index]], cities[y[index]], true);
        }
        Store[] stores = new Store[w];
        for (int index = 0; index < w; index++)
        {
            Store store = new Store(cities[c[index]], k[index], p[index]);
            stores[index] = store;
            cities[c[index]].stores.add(store);
        }
        Arrays.sort(stores, (store0, store1) -> Long.compare(store0.price, store1.price));
        int[] result = new int[q];
        for (int index = 0; index < q; index++)
        {
            result[index] = solve(cities, stores, g[index], r[index], a[index]);
        }
        return result;
    }

    public static void solve() throws IOException
    {
        int n = nextInt();
        int m = nextInt();
        int[] x = new int[m];
        int[] y = new int[m];
        for (int index = 0; index < m; index++)
        {
            x[index] = nextInt() - 1;
            y[index] = nextInt() - 1;
        }
        int w = nextInt();
        int[] c = new int[w];
        int[] k = new int[w];
        int[] p = new int[w];
        for (int index = 0; index < w; index++)
        {
            c[index] = nextInt() - 1;
            k[index] = nextInt();
            p[index] = nextInt();
        }
        int q = nextInt();
        int[] g = new int[q];
        int[] r = new int[q];
        int[] a = new int[q];
        for (int index = 0; index < q; index++)
        {
            g[index] = nextInt() - 1;
            r[index] = nextInt();
            a[index] = nextInt();
        }
        int[] result = solve(n, m, x, y, w, c, k, p, q, g, r, a);
        for (int index = 0; index < q; index++)
        {
            out.println(result[index]);
        }
    }
}
