#include<bits/stdc++.h>
using namespace std;
const int N=6e5+10,inf=1e9;
struct node{
	int from,to,val;
}e[N];
struct node2{
	int v,w;
};
int n,m,kk;
int head[N],fat[N],d[N],fa[N][30],ans[N][30],vis[N];
vector<node2> g[N];
bool cmp(node a,node b){
	return a.val>b.val;
}
int fd(int x){
	if(fat[x]==x){
		return x;
	}
	return fat[x]=fd(fat[x]);
}
void dfs(int u,int f){
	vis[u]=1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].v,w=g[u][i].w;
		if(v==f||vis[v]){
			continue;
		}
		d[v]=d[u]+1;
		fa[v][0]=u;
		ans[v][0]=w;
		for(int j=1;j<=kk;j++){
			fa[v][j]=fa[fa[v][j-1]][j-1];
			ans[v][j]=min(ans[v][j-1],ans[fa[v][j-1]][j-1]);
		}
		dfs(v,u);
	}
}
int lca(int u,int v){
	int res=inf;
	if(fd(u)!=fd(v)){
		cout<<fd(u)<<" "<<fd(v)<<endl;
		return -1;
	}
	if(d[u]>d[v]){
		swap(u,v);
	}
	for(int i=kk;i>=0;i--){
		if(d[fa[v][i]]>=d[u]){
			res=min(res,ans[v][i]);
			v=fa[v][i];
		}
	}
	if(u==v){
		return res;
	}
	for(int i=kk;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			res=min(res,min(ans[u][i],ans[v][i]));
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	res=min(res,min(ans[u][0],ans[v][0]));
	return res;;
}
signed main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0),cout.tie(0);
//	freopen("P1967_1.in.txt","r",stdin);
//	freopen("1.out","w",stdout);
	cin>>n>>m;
	kk=log2(n);
	memset(ans,0x3f,sizeof(ans));
	for(int i=1;i<=n;i++){
		fat[i]=i;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>e[i].from>>e[i].to>>e[i].val;
	}
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++){
		int xf=fd(e[i].from),yf=fd(e[i].to);
		if(xf==yf){
			continue;
		}
		fat[xf]=yf;
		g[xf].push_back({yf,e[i].val});
		g[yf].push_back({xf,e[i].val});
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i,-1);
		}
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		cout<<lca(u,v)<<endl;
	}
}

wa on #14 #16 #17

求调玄关