[Template] Minimum Bottleneck Spanning Tree (Hard Version)

Problem Description

You are given an undirected graph with $n$ vertices and $m$ edges, each edge having a weight. Define the bottleneck of a path from vertex $i$ to vertex $j$ as the maximum weight on that path. There are $q$ queries; each query gives two vertices $(s, t)$. For each query, find the minimum bottleneck over all paths from $s$ to $t$.

It is guaranteed that the graph is connected.

Input Format

The first line contains two positive integers $n$ ($1 \le n \le 10^5$) and $m$ ($1 \le m \le \min(10^6, \frac{n \times (n-1)}{2})$), the numbers of vertices and edges.

Lines $2$ to $m+1$ each contain three integers $x, y, d$ ($0 \le d \le 10^9$), denoting an undirected edge of weight $d$ between $x$ and $y$.

Line $m+2$ contains a positive integer $q$ ($1 \le q \le 10^6$), the number of queries. The following $q$ lines each contain two positive integers $s, t$ ($1 \le s, t \le n$), the start and end vertices.

Output Format

For each query, output one integer on its own line: the minimum bottleneck.

Note: Because the input and output sizes of this problem are very large, please use fast I/O.

Sample Input

2 1
1 2 10
1
1 2

Sample Output

10