#include<bits/stdc++.h>
#define N 5010
using namespace std;
//basic set
int head[N],headp[N],dep[N],vis[N],zu[N],mm[N],dis[N][20],mi[N][20];
int cnt=1,cntp,n,m,q;
struct abc{
	int to,nxt,w,we;
}e[N*2],ep[N*2];
void add(int u,int v,int w){
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].we=w;
	head[u]=cnt; 
}
void addp(int u,int v,int w){
	ep[++cntp].nxt=headp[u];
	ep[cntp].to=v;
	ep[cntp].w=w;
	headp[u]=cntp;
}
//max_flow part
void bfs(int x){
	queue<int>q;
	dep[x]=1;
	q.push(x);
	while(!q.empty()){
		int qd=q.front();
		q.pop();
		for(int i=head[qd];i;i=e[i].nxt){
			int v=e[i].to;
			if(dep[v]||e[i].w==0) continue;
			q.push(v);
			dep[v]=dep[qd]+1;
		}
	}
}
int dfs(int u,int mip,int t){
	if(u==t) return mip;
	int sum=0;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(e[i].w==0||dep[u]!=dep[v]-1)continue;
		int qdd=dfs(v,min(mip,e[i].w),t);
		if(qdd!=0){
			mip-=qdd;
			e[i].w-=qdd;
			e[i^1].w+=qdd;
			sum+=qdd;
		}
		if(!mip) break;
	}
	if(!sum) dep[u]=100000000;
	return sum;
}
int max_flow(int s,int t){
	int ans=0;
	while(1){
    	memset(dep,0,sizeof(dep));
    	bfs(s);
    	if(!dep[t]) break;
    	ans+=dfs(s,2e9,t);
    }
    return ans;
}
//fen zhi
void fenz(int l,int r){
	if(l>=r)return ;
	int s=zu[l],t=zu[r],cnt1=l-1,cnt2=r+1;
	for(int i=1;i<=cnt;i++)e[i].w=e[i].we;
	int w=max_flow(s,t);
	addp(s,t,w);addp(t,s,w);
	for(int i=l;i<=r;i++){
		if(dep[zu[i]])cnt1++,mm[cnt1]=zu[i];
		else cnt2--,mm[cnt2]=zu[i];
	}
	for(int i=l;i<=r;i++)zu[i]=mm[i];
	fenz(l,cnt1);
	fenz(cnt2,r);
}
//lca + shortest edge
void dfsp(int u,int fa){
	dep[u]=dep[fa]+1;
	for(int i=1;i<=19;i++)dis[u][i]=dis[dis[u][i-1]][i-1],mi[u][i]=min(mi[u][i-1],mi[dis[u][i-1]][i-1]);
	for(int i=headp[u];i;i=ep[i].nxt){
		int v=ep[i].to;
		if(v==fa)continue;
		dis[v][0]=u;
		mi[v][0]=ep[i].w;
		dfsp(v,u);
	}
}
int lca(int x,int y){
	int minn=2e8;
	if(dep[x]<dep[y])swap(x,y);
	for(int cntx=19;cntx>=0;cntx--){
		if(dep[dis[x][cntx]]>=dep[y])minn=min(minn,mi[x][cntx]),x=dis[x][cntx];
		if(x==y)return minn;
	}
	for(int cntx=19;cntx>=0;cntx--){
		if(dis[x][cntx]!=dis[y][cntx])minn=(minn,min(mi[x][cntx],mi[y][cntx])),x=dis[x][cntx],y=dis[y][cntx];
	}
	return min(minn,min(mi[x][0],mi[y][0]));
	
}
//main
int main(){
//	freopen("E:/8.in","r",stdin);
//	freopen("E:/my.out","w",stdout);
	scanf("%d%d",&n,&m);//n++;
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);//u++,v++;
		add(u,v,w);add(v,u,w);
	}
	for(int i=1;i<=n;i++)zu[i]=i;
	fenz(1,n);
	memset(dep,0,sizeof dep);
	memset(mi,0x3f,sizeof mi);
	dfsp(1,0);
	scanf("%d",&q);
	for(int i=1,u,v;i<=q;i++){
		scanf("%d%d",&u,&v);//u++,v++;
		printf("%d\n",lca(u,v));
	}
}

求助，感谢