erp

Problem Description

It's the year 2300 and the Land and Transport Authority of Singapore (LTA Singapore) has decided to construct more roads to the city. However, roads now have Electronic Road Pricing (ERP) gantries which requires the drivers to pay a certain fee whenever they travel on this road. The ERP fee will be the same for both sides of traffic and all roads are bi-directional.

Currently, roads are modelled as a graph of N nodes and E edges, with nodes being the intersection of roads/destinations and edges being the roads that all have a certain non-negative ERP fee (≥ $0). Nodes are labelled from 0 to N-1 where node 0 represents the residential areas and node N-1 represents the city.

For simplicity, it is assumed that all traffic originate from node 0 and their destination is node N-1 or vice-versa.

LTA wants to build one more road and has shortlisted K possible pairs of nodes to construct a road between. It is guaranteed that there is no direct road connecting each pair of K nodes in the original graph.

But, what use is there to construct a road that no one will use? It is known that Singaporeans are very prudent and will always travel the path of least cost. Thus, for each road that is shortlisted, LTA wants to know what is the maximum ERP fee they can set for that road such that the cost of travelling from the residential areas to the city is reduced.

Do note that the ERP fee must be a non-negative integer and if setting the ERP fee at $0 will be unable to reduce the cost of travelling from the residential areas to the city, output -1 for that planned road instead.

Input

The first line of input consists of 2 integers, N followed by E

Subsequent E lines consist 3 integers per line, A, B and F, indicating that there is a road (edge) from node A to node B with an ERP fee of $F

There will not be repeated edges. Eg. there will not be more than one edge between any 2 nodes in the input.

This will be followed by a line containing a single integer, K.

Subsequent K lines will consist of 2 integers each, X and Y. This indicates that a road between node X and node Y is shortlisted.

Output

For each shortlisted road, print out the maximum ERP fee LTA can set such that the cost of travelling from node 0 to node N-1 is reduced.

If this is not possible, output -1 for that particular shortlisted road instead.

Limits

Each ERP fee of the original road will be an integer from 0 to 1000 (inclusive). However, the maximum ERP fee in your answer can exceed 1000.

It is guaranteed that there is a indirect or direct path from the residential area to the city before the construction of the extra road.

Subtasks

Subtask 1 (37%): 2 ≤ N ≤ 50000, 1 ≤ E ≤ 100000, K = 1

Subtask 2 (26%): 2 ≤ N ≤ 50000, E = N-1, K ≤ 100000. Furthermore, the original graph is guaranteed to be a line where there will be an edge from node i to node i+1 for all 0 ≤ i < N-1

Subtask 3 (37%): 2 ≤ N ≤ 50000, 1 ≤ E ≤ 100000, K ≤ 100000

Subtask 4 (0%): Sample Testcases

Sample Input 1

5 4
0 1 1
1 2 1
2 3 1
3 4 1
12
0 2
0 3
0 4
1 3
1 4
2 0
2 4
3 0
3 1
4 0
4 1
4 2

Sample Output 1

1
2
3
1
2
1
1
2
1
3
2
1