题目描述
给定一张 n 个点 m 条边的无向图,每条边有一个权值,定义瓶颈路权值为某一条从点 i 到 j 的路径上的最大权值,有 q 个询问,每次询问给出两个点 (s,t),求从 s 到 t 的最小瓶颈路权值。
保证图联通。
输入格式
第一行包含两个正整数 n(1≤n≤105) 和 m(1≤m≤min(106,2n×(n−1)),表示点数和边数。
第二行到第 m+1 行包含三个整数 x,y,d(0≤d≤109),表示 x 和 y 之间连有一条权值为 d 的无向边。
第 m+2 包含一个正整数 q(1≤q≤106),表示询问的次数,后面 q 行每行两个正整数 s,t(1≤s,t≤n),分别表示起点和终点。
输出格式
对于每次询问,每行输出一个整数,表示最小的瓶颈路权值
**注意:**由于本道题输入输出规模过大,请注意 IO 优化
样例输入
2 1
1 2 10
1
1 2
样例输出
10