rt

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int s=0,w=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')w=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
	return s*w;
}
inline void print(int x)
{
	if(x<0)x=-x,putchar('-');
	if(x>=10)print(x/10);
	putchar(x%10+48);
}
int n,m;
struct node{
	int v,w,next;
}e[1000010],g[1000010];
int eid=0,head[1000010],Head[1000010],tmp[1000010],dis[1000010],a[1000010],c[1000010],x[1000010],y[1000010],W[1000010],V,m1,m2,idx=1;
const int inf=1e15;
int f[100010][20],w[100010][20],dep[100010];
inline void insert(int u,int v,int w)
{
	e[eid].v=v;
	e[eid].w=w;
	e[eid].next=head[u];
	head[u]=eid++;
}
inline void add(int u,int v,int w)
{
	g[idx].v=v;
	g[idx].w=w;
	g[idx].next=Head[u];
	Head[u]=idx++;
}
int s,t;
inline bool bfs()
{
	for(int i=1;i<=n;i++)head[i]=tmp[i],dis[i]=inf;
	dis[s]=0;
	queue<int> q;
	q.push(s);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];~i;i=e[i].next)
		{
			int v=e[i].v,w=e[i].w;
			if(!w)continue;
			if(dis[v]==inf)
			{
				dis[v]=dis[u]+1;
				q.push(v);
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
inline int dinic(int u,int sum)
{
	if(u==t)return sum;
	int res=0;
	for(int i=head[u];(~i)&&sum;i=e[i].next)
	{
		head[u]=i;
		int v=e[i].v,w=e[i].w;
		if(!w)continue;
		if(dis[v]==dis[u]+1)
		{
			int k=dinic(v,min(w,sum));
			e[i].w-=k;
			e[i^1].w+=k;
			res+=k;
			sum-=k;
		}
	}
	return res;
}
inline void work()
{
	if(V==1)return;
	eid=0;
	for(int i=1;i<=n;i++)head[i]=-1;
	for(int i=1;i<=m;i++)
	{
		int u=x[i],v=y[i],w=W[i];
		//cout<<"llian:"<<u<<" "<<v<<" "<<w<<" "<<eid<<"\n";
		insert(u,v,w);
		insert(v,u,0);
		insert(v,u,w);
		insert(u,v,0);
	}
	for(int i=1;i<=n;i++)tmp[i]=head[i];
	int sum=0;
	while(bfs())sum+=dinic(s,inf);
	add(s,t,sum);
	add(t,s,sum);
	int b[510],d[510],tmpV=V;
	m1=0;
	for(int i=1;i<=V;i++)
	{
		b[i]=a[i];
		if(dis[a[i]]==inf)c[++m1]=a[i];
		d[a[i]]=dis[a[i]];
	}
	V=m1;
	for(int i=1;i<=m1;i++)a[i]=c[i];
	s=a[1];
	t=a[m1];
	work();
	m1=0;
	for(int i=1;i<=tmpV;i++)if(d[b[i]]<inf)a[++m1]=b[i];
	s=a[1];
	t=a[m1];
	V=m1;
	work();
}
inline void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	for(int i=Head[u];i;i=g[i].next)
	{
		int v=g[i].v;
		if(v==fa)continue;
		dfs(v,u);
		w[v][0]=g[i].w;
		f[v][0]=u;
	}
}
inline int query(int a,int b)
{
	int mi=0x3f3f3f3f;
	if(dep[a]<dep[b])swap(a,b);
	for(int i=19;i>=0;i--)
	{
		if(dep[f[a][i]]>=dep[b])
		{
			mi=min(mi,w[a][i]);
			a=f[a][i];
		}
	}
	if(a==b)return mi;
	for(int i=19;i>=0;i--)
	{
		if(f[a][i]!=f[b][i])
		{
			mi=min({mi,w[a][i],w[b][i]});
			a=f[a][i];
			b=f[b][i];
		}
	}
	return min({mi,w[a][0],w[b][0]});
}
signed main()
{
	memset(head,-1,sizeof(head));
	n=read();
	m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		x[i]=u;
		y[i]=v;
		W[i]=w;
	}
	s=1,t=n;
	V=n;
	for(int i=1;i<=n;i++)a[i]=i;
	work();
	dfs(1,0);
	for(int j=1;j<=19;j++)
	{
		for(int i=1;i<=n;i++)
		{
			f[i][j]=f[f[i][j-1]][j-1];
			w[i][j]=min(w[i][j-1],w[f[i][j-1]][j-1]);
		}
	}
	int q=read();
	while(q--)
	{
		int u=read(),v=read();
		print(query(u,v));
		puts("");
	}
}