Minimizing Maximum Edge Danger

You are given a weighted undirected graph with \(N\) vertices and \(M\) edges. Each vertex represents a galaxy and an edge between two vertices indicates that there is a direct flight between the corresponding galaxies. The weight on each edge represents the danger level of that direct flight.

For a given set of queries, each query is specified by two vertices \(A\) and \(B\). Your task is to determine a path from \(A\) to \(B\) such that the maximum danger level (i.e. the maximum edge weight along that path) is minimized. If there is no path connecting \(A\) and \(B\), output \(-1\) for that query.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of vertices and edges, respectively.

The next \(M\) lines each contain three integers \(u\), \(v\), and \(w\), indicating that there is an edge between vertices \(u\) and \(v\) with danger level \(w\).

The following line contains an integer \(Q\), the number of queries.

Each of the next \(Q\) lines contains two integers \(A\) and \(B\), representing a query to determine the minimum possible maximum edge weight on any path from \(A\) to \(B\).

outputFormat

For each query, print a single line containing the minimum possible maximum danger level along any path from \(A\) to \(B\). If there is no path connecting \(A\) and \(B\), output \(-1\).

sample

4 4
1 2 3
2 3 4
3 4 5
1 4 10
3
1 3
2 4
1 4

4
5
5