样例能过，但是 TLE 点1 WA 点2 其余全部MLE

做法是最大生成树加 LCA

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9;
const int M = 5e4+100;
const int N = 1e5+100;

void read (int &x) {
    int f = 1;x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') { x = x*10+ch-'0'; ch = getchar();}
    x *= f;
}

void print (int x) {
    if (x<0) putchar('-'), x = -x;
    if (x<10) putchar(x+'0');
    else print(x/10), putchar(x%10+'0');
}

struct R {
	int u, v, w, lst;
}road[M], tr[N];

int n, m, q, final[N], tot, fa[N][21], w[N][21], dep[N], father[N], lg[N];
bool check[N];

void add (int u, int v, int w) { tr[++tot].u = u, tr[tot].v = v, tr[tot].w = w, tr[tot].lst = final[u], final[u] = tot; }

bool cmp (R a, R b) { return a.w > b.w; }

int find (int x) {
	if (father[x] == x) return x;
	return father[x] = find(father[x]);
}

//void merge (int a, int b) {
//	int f_a = find(a), f_b = find(b);
//	if (f_a != f_b) father[f_a] = f_b;
//}

void kruskal () {
	for (int i = 1;i <= n;i++) father[i] = i;
	for (int i = 1;i <= m;i++) {
		int u = road[i].u, v = road[i].v;
		if (find(u) != find(v)) father[find(u)] = father[find(v)], add(u, v, road[i].w), add(v, u, road[i].w);
	}
}

void dfs (int now, int rt) {
	fa[now][0] = rt;
	dep[now] = dep[rt]+1;
	check[now] = true;
	for (int i = final[now];i;i = tr[i].lst) if (!check[road[i].v]) w[tr[i].v][0] = tr[i].w, dfs(tr[i].v, now);
//	for (int i = 1;i <= lg[dep[now]];i++) fa[now][i] = fa[fa[now][i-1]][i-1], w[now][i] = min(w[now][i-1], w[fa[now][i-1]][i-1]);
}

int lca (int a, int b) {
	if (find(a) != find(b)) return -1;
	int res = INF;
	if (dep[a] < dep[b]) swap(a, b);
	while (dep[a] > dep[b]) res = min(res, w[a][lg[dep[a]-dep[b]]-1]), a = fa[a][lg[dep[a]-dep[b]]-1];
	if (a == b) return res;
	for (int i = 20;i >= 0;i--) if (fa[a][i] != fa[b][i]) res = min(res, min(w[a][i], w[b][i])), a = fa[a][i], b = fa[b][i];
	res = min(res, min(w[a][0], w[b][0]));
	return res;
}

int main () {
	//freopen("xxx.in", "r", stdin);
	//freopen("xxx.out", "w", stdout);
	read(n), read(m);
	for (int i = 1;i <= n;i++) lg[i] = lg[i-1] + ((1 << lg[i-1]) == i);
	for (int i = 1;i <= m;i++) {
		int x, y, z;
		read(x), read(y), read(z);
		road[i].u = x, road[i].v = y, road[i].w = z;
	}
	sort(road+1, road+m+1, cmp);
	kruskal();
	for (int i = 1;i <= n;i++) {
		if (!check[i]) {
			dep[i] = 1, dfs(i, i);
			w[i][0] = INF;
		}
	}
	for (int i = 1;i <= 20;i++) 
		for (int j = 1;j <= n;j++) fa[j][i] = fa[fa[j][i-1]][i-1], w[j][i] = min(w[j][i-1], w[fa[j][i-1]][i-1]);
	
	read(q);
	for (int i = 1;i <= q;i++) {
		int x, y;
		read(x), read(y);
		int ans = lca(x, y);
		printf("%d\n", ans);
	}
	return 0;
}