本题有一个重要的性质。一辆车从一个点走到另一个点经过的边为了使得尽量走边权更大的路线，最优解是在最大生成树上的边去行走。

考虑反证法，若我们最优解可以不经过最大生成树的边而走别的某一条边可以造成答案更优。那么根据最大生成树的求解过程，一定存在某一条边我们将其替换为更大的那条边，使得生成树更优，则说明我们生成树求的不对，和假设在最大生成树上走矛盾。

有了这个性质以后，我们预处理出最大生成树，并且建立一棵树，由于树上任意两点之间路径唯一，我们可以将路线分为两部分。

• 从起点 $s$ 先走到 LCA，再从 LCA 走到终点 $t$

于是我们可以使用倍增预处理 LCA 的同时，再去维护任意两点之间路径边权的最小值即可。

本题还有一些细节要注意

• 图不连通，建树可能也不连通，因此对于没有搜过的点都要搜索
• 无解的情况即两点不连通，可以使用并查集判断

#include <bits/stdc++.h>
#define ll long long
#define p pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1e4 + 5;
int n, m, f[N][14], g[N][14], de[N], q;
vector<p> e[N];
int fa[N];
bool st[N];
struct edge
{
    int u, v, w;
    bool operator < (const edge&x) const
    {
        return w > x.w;
    }
};
vector<edge> adj;
int find(int x)
{
    return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    x = find(x), y = find(y);
    fa[x] = y;
}
void dfs(int u, int father)
{
    st[u] = 1;
    for (auto nxt : e[u])
    {
        int v = nxt.x, w = nxt.y;
        if (v == father) continue;
        de[v] = de[u] + 1;
        f[v][0] = u, g[v][0] = w;
        for (int i = 1; (1 << i) <= n; i++) 
            f[v][i] = f[f[v][i - 1]][i - 1], g[v][i] = min(g[v][i - 1], g[f[v][i - 1]][i - 1]);
        dfs(v, u);
    }
}
int lca(int u, int v)
{
    if (de[u] < de[v]) swap(u, v);
    int mn = 1e5, h = de[u] - de[v];
    for (int i = 0; i < 14; i++)
    {
        if (h & (1 << i)) mn = min(mn, g[u][i]), u = f[u][i];
    }
    if (u == v) return mn;
    for (int i = 13; i >= 0; i--)
    {
        if (f[u][i] != f[v][i])
        {
            mn = min(mn, min(g[u][i], g[v][i]));
            u = f[u][i], v = f[v][i];
        }
    }
    return min(mn, min(g[u][0], g[v][0]));
}
void kruskal()
{
    for (auto road : adj)
    {
        int u = road.u, v = road.v, w = road.w;
        if (find(u) != find(v))
        {
            merge(u, v);
            e[u].push_back({v, w}), e[v].push_back({u, w});
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj.push_back({u, v, w});
    }
    sort(adj.begin(), adj.end());
    kruskal();
    for (int i = 1; i <= n; i++)//图可能不连通，尝试从每个点搜索
    {
        if (!st[i]) dfs(i, 0);
    }
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        if (find(u) != find(v))//二者不连通则无法到达输出-1
        {
            cout << "-1\n";
            continue;
        }
        cout << lca(u, v) << "\n";
    }
    return 0;
}