Find the Heaviest Edge in a Graph Path

Given an undirected graph with n vertices and m edges, where each edge is assigned an integer weight, your task is to answer queries of the following form:

For a given pair of vertices \( u \) and \( v \), determine the weight of the maximum edge along the path from \( u \) to \( v \) such that the overall maximum value is minimized. In other words, among all possible paths from \( u \) to \( v \), choose the one that minimizes the maximum edge weight, and return that maximum edge weight. If there is no path connecting \( u \) and \( v \), output \(-1\).

The relation can be expressed in LaTeX as follows:

\[ \text{answer} = \min_{\text{path } P \text{ from } u \text{ to } v} \; \max_{e \in P} w_e \]

Note: The graph may be disconnected. For each query, if there is no valid path, print \(-1\).

inputFormat

The input is given in the following format from stdin:

 n m
 u1 v1 w1
 u2 v2 w2
 ...
 um vm wm
 q
 u1 v1
 u2 v2
 ...
 uq vq

Here, the first line contains two integers \( n \) and \( m \) denoting the number of vertices and edges respectively. The next \( m \) lines each contain three integers \( u_i \), \( v_i \) and \( w_i \) indicating an edge between vertices \( u_i \) and \( v_i \) with weight \( w_i \). Then an integer \( q \) is given, representing the number of queries, followed by \( q \) lines, each containing two integers \( u \) and \( v \) representing a query.

outputFormat

For each query, output the weight of the heaviest edge along the minimax path from \( u \) to \( v \) on a separate line to stdout. If no path exists, output \(-1\).

5 4
1 2 10
2 3 5
3 4 8
4 5 7
3
1 5
2 4
1 3

10
8
10