bee 2768 - Dabriel's Graph

Dabriel just won a gift graph and wants to perform some operations on it, however as it is too busy decided to ask for your help. You should answer several queries of type U, V, K, where you should print the smallest path from U to V, if any, where vertices visited, excluding U and V, must be less than or equal to K.

Input

The input is composed of several test cases. The first line will have 2 integers N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ N * (N-1) / 2). In the next M lines will have 3 integers U, V, W (1 ≤ U, V ≤ N, 0 ≤ W ≤ 2 * 10³), indicating that the vertex U has a bidirectional connection with the vertex V with a cost of W. The next line will have a integer Q (1 ≤ Q ≤ 10⁵). In the next Q lines will have a query U, V, K (1 ≤ U, V, K ≤ N).

Output

For each query you should print the lowest cost following the restrictions of the text. If there is no answer, print -1.

Input Sample	Output Sample
5 6 1 2 1 2 3 3 1 4 1 4 3 2 3 5 1 1 5 50 6 1 5 1 1 5 2 1 5 3 1 5 4 1 5 5 1 3 1	50 50 5 4 4 -1