#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50010;

struct Node {
	int id, dis, from;
};

struct Edge {
	int nxt;
	int to;
	int w;
	bool vis;
} edge[MAXN * 2];
priority_queue<Node> q;
int head[MAXN], cnt;
int N, M, Q;
int minn[MAXN][15];
int fa[MAXN][15], dep[MAXN];

namespace Prim
{
	int vis[MAXN];

}// namespace Prim

namespace LCA
{
	int vis[MAXN];
}// namespace LCA

bool operator<(const Node& a, const Node& b)
{
	return a.dis < b.dis;
}

void link(int u, int v, int w)
{
	edge[++cnt].nxt = head[u];
	edge[cnt].to = v;
	edge[cnt].w = w;
	head[u] = cnt;
}

void prim()
{
	for (int i = 1; i <= N; i++) {
		if (Prim::vis[N]) continue;
		q.push(Node{i, 0, 0});
		while (!q.empty()) {
			Node u = q.top();
			q.pop();
			if (Prim::vis[u.id]) continue;
			Prim::vis[u.id] = 1;
			edge[u.from].vis = 1;
			if (u.from & 1) edge[u.from + 1].vis = 1;
			else
				edge[u.from - 1].vis = 1;
			for (int i = head[u.id]; i; i = edge[i].nxt) {
				int to = edge[i].to;
				int w = edge[i].w;
				int from = i;
				if (Prim::vis[to]) continue;
				q.push(Node{to, w, from});
			}
		}
	}
}

void dfs(int x, int father, int w)
{
	if (LCA::vis[x]) return;
	LCA::vis[x] = 1;
	fa[x][0] = father;
	minn[x][0] = w;
	dep[x] = dep[father] + 1;
	for (int i = 1; (1 << i) <= 14; i++) {
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
		minn[x][i] = min(minn[x][i - 1], minn[minn[x][i - 1]][i - 1]);
	}
	for (int i = head[x]; i; i = edge[i].nxt) {
		int to = edge[i].to;
		int cw = edge[i].w;
		if (to == father) continue;
		if (!edge[i].vis) continue;//必须是最大生成树上有的边
		dfs(to, x, cw);
	}
}

int getlca(int a, int b)
{
	int ans = 0x7fffffff;
	if (dep[a] < dep[b]) swap(a, b);
	for (int i = 14; i >= 0; i--) {
		if (dep[a] - (1 << i) >= dep[b]) {
			ans = min(ans, minn[a][i]);
			a = fa[a][i];
		}
	}
	if (a == b) return ans;
	for (int i = 14; i >= 0; i--) {
		if (fa[a][i] == fa[b][i]) continue;

		ans = min(ans, min(minn[a][i], minn[b][i]));
		a = fa[a][i], b = fa[b][i];
	}
	if (fa[a][0] == 0) return -1;
	return min(ans, min(minn[a][0], minn[b][0]));
}

int main()
{
	freopen("input", "r", stdin);
	freopen("output", "w", stdout);
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		link(u, v, w);
		link(v, u, w);
	}
	//使用prim求最大生成树
	prim();
	cin >> Q;
	memset(minn, 0x3f, sizeof(minn));
	for (int i = 1; i <= N; i++) {
		dfs(i, 0, 0);
	}
	//倍增LCA
	for (int i = 1; i <= Q; i++) {
		int a, b;
		cin >> a >> b;
		cout << getlca(a, b) << endl;
	}
	return 0;
}

第三个点输入:

10 24
4 7 19038
7 10 7375
7 9 17853
9 8 6341
7 2 16976
10 3 2835
10 4 19285
9 4 29193
3 4 4852
3 8 16597
9 1 4138
9 7 21611
7 4 10586
10 4 7821
10 9 25636
3 9 28425
2 3 17229
4 8 11331
9 2 25053
6 4 929
8 3 1738
10 9 28542
1 2 28343
3 5 13215
9
7 5
2 4
10 2
5 10
7 10
4 3
10 1
10 4
8 4

输出：

13215
29193
28542
13215
21611
28425
28343
28542
16597

答案：

13215
25053
25053
13215
21611
28425
25053
28542
16597