#include<bits/stdc++.h>
using namespace std;
struct edge{int to,flow;}e[3005];
int n,m,used=0,dis[505];
vector<int> g[505];
void addedge(int u,int v,int w)
{
	e[used]={v,w};g[u].push_back(used);used++;
	e[used]={u,w};g[v].push_back(used);used++;
}
int to,bg,en,que[505],cur[505];
bool prepare(int st,int To)
{
	memset(dis,0x3f,sizeof dis);
	memset(cur,0,sizeof cur);
	to=To;bg=en=0;que[bg]=st;dis[st]=0;
	while(bg<=en)
	{
		int qf=que[bg];
		for(int i:g[qf])
			if(e[i].flow and dis[e[i].to]>dis[qf]+1)
			{
				dis[e[i].to]=dis[qf]+1;
				en++;que[en]=e[i].to;
			}
		bg++;
	}
	return dis[to]<=n;
}
int dinic(int st,int flow)
{
	if(flow==0 or st==to)return flow;
	if(dis[st]>=dis[to])return 0;
	int tot=0;
	for(;cur[st]<(int)g[st].size();cur[st]++)
	{
		int i=cur[st];edge neg=e[g[st][i]];
		if(neg.flow==0 or dis[neg.to]<dis[st]+1)continue;
		int tmp=dinic(neg.to,min(flow,neg.flow));
		tot+=tmp;flow-=tmp;
		e[g[st][i]].flow-=tmp;
		e[g[st][i]^1].flow+=tmp;
	}
	return tot;
}
int cut[505][505],id[505];
void getcut(int l,int r)
{
	if(l>=r)return;
	for(int i=0;i<used;i+=2)
		e[i].flow=e[i^1].flow=(e[i].flow+e[i^1].flow)/2;
	int res=0,St=id[l],To=id[r];
	while(prepare(St,To))res+=dinic(St,To);
	int sep=l;
	for(int i=l+1;i<=r;i++)
		if(dis[id[i]]<=n)
		{
			sep++;
			swap(id[sep],id[i]);
		}
	getcut(l,sep);
	getcut(sep+1,r);
	cut[St][To]=res;
	for(int i=l;i<=sep;i++)
	{
		int x=id[i];
		for(int j=sep+1;j<=r;j++)
		{
			int y=id[j];
			cut[x][y]=cut[y][x]=min({cut[x][St],cut[St][To],cut[To][y]});
		}
	}
}
int main()
{
	memset(cut,0x3f,sizeof cut);
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
	}
	for(int i=1;i<=n;i++)id[i]=i;
	getcut(0,n);
	int Q;
	for(scanf("%d",&Q);Q;Q--)
	{
		scanf("%d%d",&u,&v);
		printf("%d\n",cut[u][v]);
	}
	return 0;
}