code：

//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define rg register int
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pp;
//inline int rd()
//{
//	int s=0,w=1;
//	char ch=getchar();
//	while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
//	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
//	return s*w;
//}
//inline void wt(int x)
//{
//	if(x<0) putchar('-'),x=-x;
//	if(x>=10) wt(x/10);
//	putchar(x%10+'0');
//}
const int N=5110,M=15110;
int n,m,q;
struct edge
{
	int x,y,z;
}e[M];
int h[N],sum;
struct node
{
	int to,nxt,w;
}a[M<<2],at[N<<1];
int ht[N],sumt;
inline void addt(int x,int y,int z)
{
	sumt++;
	at[sumt].to=y;
	at[sumt].nxt=ht[x];
	at[sumt].w=z;
	ht[x]=sumt;
}
inline void add(int x,int y,int z)
{
	sum++;
	a[sum].to=y;
	a[sum].nxt=h[x];
	a[sum].w=z;
	h[x]=sum;
	sum++;
	a[sum].to=x;
	a[sum].nxt=h[y];
	a[sum].w=0;
	h[y]=sum;
}
int dis[N],b[N],head,tail,now[N];
int S,T;
inline int dfs(int x,int l)
{
	if(x==T) return l;
	int c=0;
	for(rg i=now[x];i&&l;i=a[i].nxt)
	{
		now[x]=i;
		int y=a[i].to;
		if(a[i].w&&dis[y]==dis[x]+1)
		{
			int u=dfs(y,min(a[i].w,l));
			if(u==0) dis[y]=2e9;
			l-=u;
			c+=u;
			if(i^1) a[i+1].w+=u,a[i].w-=u;
			else a[i-1].w+=u,a[i].w-=u;
		}
	}
	return c;
}
inline int dinic()
{
	sum=0;
	for(rg i=1;i<=n;i++) h[i]=0;
	for(rg i=1;i<=m;i++) add(e[i].x,e[i].y,e[i].z),add(e[i].y,e[i].x,e[i].z);
	int ans=0;
	while(1)
	{
		for(rg i=1;i<=n;i++) dis[i]=0,now[i]=h[i];
		head=0;
		tail=1;
		b[1]=S;
		dis[S]=1;
		while(head<tail)
		{
			head++;
			int x=b[head];
			for(rg i=h[x];i;i=a[i].nxt)
			{
				int y=a[i].to;
				if(a[i].w>0&&!dis[y])
				{
					dis[y]=dis[x]+1;
					tail++;
					b[tail]=y;
				}
			}
		}
		if(!dis[T]) return ans;
		ans+=dfs(S,2e9);
	}
}
int d[N];
int tmp1[N],tmp2[N];
inline void aa(int l,int r)
{
	if(l==r) return ;
	S=d[l];T=d[l+1];
	int u=dinic();
	addt(S,T,u);addt(T,S,u);
	int len1=0,len2=0;
	for(rg i=l;i<=r;i++)
	if(dis[d[i]]) tmp1[++len1]=d[i];
	else tmp2[++len2]=d[i];
	for(rg i=1;i<=len1;i++) d[l+i-1]=tmp1[i];
	for(rg i=1;i<=len2;i++) d[l+len1+i-1]=tmp2[i];
	aa(l,l+len1-1);
	aa(l+len1,r);
}
pp fa[N];
int dep[N];
inline void dfs1(int x)
{
	for(rg i=ht[x];i;i=at[i].nxt)
	{
		int y=at[i].to;
		if(y!=fa[x].fi)
		{
			fa[y]={x,at[i].w};
			dep[y]=dep[x]+1;
			dfs1(y);
		}
	}
}
int main()
{
//	freopen("","r",stdin);
//	freopen("","w",stdout);
	scanf("%d%d",&n,&m);
	for(rg i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
	for(rg i=1;i<=n;i++) d[i]=i;
	aa(1,n);
	dfs1(1);
	scanf("%d",&q);
	while(q--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		int ans=2e9;
		while(x!=y)
		{
			if(dep[x]>dep[y])
			{
				ans=min(ans,fa[x].se);
				x=fa[x].fi;
			}
			else
			{
				ans=min(ans,fa[y].se);
				y=fa[y].fi;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}