403223: GYM101081 F Auction of Services

It is becoming more common to use strategies based on social networks for shopping, contract services, arrange meetings, etc. Such strategies often involve interesting mathematical knowledge, like Game Theory. A new trend has appeared, the use of social networks to carry out virtual auctions to contract services. The service providers have agreements between them that enforce a service to cost a predetermine value. The prices a company charges, when it works in collaboration with each of its partners, can be very different, since many factors such as location, previous partnerships, tradition, etc. influence the convenience of a particular partnership.

In this problem you want to estimate the price of a service given by a couple of service providers. It is already known the price of the service given by some companies that have an agreement to work together. Furthermore, if we have two companies A and B, we can contract a service (offered by them) using a chain of companies c₁, c₂, ... c_k, such that

• c_i and c_i + 1 have an agreement, for i = 1, ..., k - 1,
• c₁ = A and c_k = B.

Also, we know that the price to contract such chain of companies, is the highest price of a service given by a pair of adjacent companies in that chain. That's the power of social networks!

In the previous figure, despite the fact that the price of the agreement between A and C is 13, the best price (in the network that links these companies) is 9, using the agreements through B.

Your task is to help these virtual auctions. The person interested in contracting a certain service chooses a pair of companies he want to contract, and you need to make a program that answers the minimum possible price of that service.

The first line contains two integers N and M, the number of companies and agreements, respectively. The companies are numbered from 1 to N. Each of the following M lines contains three integers, the ith contains A_i, B_i and C_i, indicating that there is an agreement between companies A_i and B_i whose price is C_i. Each pair of companies has at most one agreement. It is guaranteed it is possible to contract a service between any pair of companies.

The next line contains an integer Q, the number of queries. The following Q lines contain a pair of integers representing the companies which we want to contract.

Limits

• 2 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 2·10⁵
• 1 ≤ A_i ≠ B_i ≤ N
• 1 ≤ C_i ≤ 10⁶
• 1 ≤ Q ≤ 2·10⁵

Print Q integers representing the price of the service for each query.

4 4
1 2 6
1 3 1
2 4 2
3 4 2
2
1 2
1 4

2
2

4 4
1 2 1
2 3 7
2 4 3
3 4 4
4
1 3
1 4
3 2
4 2

4
3
4
3