【模板】最小瓶颈生成树（数据加强版）

题目描述

给定一张 $n$ 个点 $m$ 条边的无向图，每条边有一个权值，定义瓶颈路权值为某一条从点 $i$ 到 $j$ 的路径上的最大权值，有 $q$ 个询问，每次询问给出两个点 $(s,t)$，求从 $s$ 到 $t$ 的最小瓶颈路权值。

保证图联通。

输入格式

第一行包含两个正整数 $n(1\leq n\le 10^5)$ 和 $m (1\leq m\leq \min(10^6, \frac{n \times (n-1)}{2})$，表示点数和边数。

第二行到第 $m+1$ 行包含三个整数 $x,y,d(0\leq d\leq 10^9)$，表示 $x$ 和 $y$ 之间连有一条权值为 $d$ 的无向边。

第 $m+2$ 包含一个正整数 $q(1\leq q\leq 10^6)$，表示询问的次数，后面 $q$ 行每行两个正整数 $s,t(1\leq s, t\leq n)$，分别表示起点和终点。

输出格式

对于每次询问，每行输出一个整数，表示最小的瓶颈路权值

**注意：**由于本道题输入输出规模过大，请注意 IO 优化

样例输入

2 1 
1 2 10
1
1 2

样例输出

10