#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstdlib>
#include<random>
#define N 6000000
#define M 4194303
using namespace std;
mt19937 RAND(random_device{}());
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data;
};
struct node
{
	int x,y,data,nxt;
};
node edge[N+1],edge2[N+1],edge3[N+1];
int n,m,q,len,len2,len3,X[N+1],Y[N+1],Z[N+1],rd[N+1],rd2[N+1],head[M+1],head2[M+1],head3[M+1],deg[N+1],rk[N+1],length,sx[N+1],sy[N+1],ans[N+1];
queue<int>qs;
vector<int>E[N+1];
vector<reads>ES[N+1];
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x),deg[x]++,deg[y]++;
	return;
}
void insert(int x,int y,int d)
{
	if (x>y) swap(x,y);
	int ds=rd[x]^rd2[y];
	for (int i=head[ds];i>0;i=edge[i].nxt)
		if (edge[i].x==x&&edge[i].y==y)
		{
			edge[i].data=min(edge[i].data,d);
			return;
		}
	edge[++len]=(node){x,y,d,head[ds]},head[ds]=len;
	return;
}
int query(int x,int y)
{
	if (x>y) swap(x,y);
	int ds=rd[x]^rd2[y];
	for (int i=head[ds];i>0;i=edge[i].nxt)
		if (edge[i].x==x&&edge[i].y==y)
			return edge[i].data;
	return inf;
}
void insert2(int x,int y,int d)
{
	if (x>y) swap(x,y);
	int ds=rd[x]^rd2[y];
	edge2[++len2]=(node){x,y,d,head2[ds]},head2[ds]=len2;
	return;
}
int query2(int x,int y)
{
	if (x>y) swap(x,y);
	int ds=rd[x]^rd2[y];
	for (int i=head2[ds];i>0;i=edge2[i].nxt)
		if (edge2[i].x==x&&edge2[i].y==y)
			return edge2[i].data;
	return inf;
}
void insert3(int x,int y,int d)
{
	if (x>y) swap(x,y);
	int ds=rd[x]^rd2[y];
	edge3[++len3]=(node){x,y,d,head2[ds]},head3[ds]=len3;
	return;
}
int query3(int x,int y)
{
	if (x>y) swap(x,y);
	int ds=rd[x]^rd2[y];
	for (int i=head3[ds];i>0;i=edge3[i].nxt)
		if (edge3[i].x==x&&edge3[i].y==y)
			return edge3[i].data;
	return inf;
}
int main()
{
	int top;
	n=read(),m=read();
	for (int i=1;i<=n;++i) rd[i]=RAND()&M,rd2[i]=RAND()&M;
	for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),Z[i]=read(),add(X[i],Y[i]),insert2(X[i],Y[i],Z[i]);
	q=read();
	for (int i=1;i<=q;++i) sx[i]=read(),sy[i]=read(),ans[i]=inf;
	for (int i=1;i<=m;++i) insert(X[i],Y[i],Z[i]),insert2(X[i],Y[i],Z[i]);
	for (int i=1;i<=q;++i) insert3(sx[i],sy[i],i);
	for (int i=1;i<=n;++i)
		if (deg[i]<=5)
			qs.push(i);
	while (!qs.empty())
	{
		top=qs.front(),qs.pop(),rk[top]=++length;
		for (int i=0;i<E[top].size();++i)
			if (deg[E[top][i]]>5)
			{
				deg[E[top][i]]--;
				if (deg[E[top][i]]==5) qs.push(E[top][i]);
			}
	}
	for (int i=1;i<=m;++i)
	{
		if (rk[X[i]]<rk[Y[i]]) ES[X[i]].push_back((reads){Y[i],Z[i]});
		else ES[Y[i]].push_back((reads){X[i],Z[i]});
	}
	for (int i=1;i<=n;++i)
		for (int j=0;j<ES[i].size();++j)
			for (int k=j+1;k<ES[i].size();++k)
				insert(ES[i][j].num,ES[i][k].num,ES[i][j].data+ES[i][k].data);
	for (int i=1;i<=q;++i)
	{
		for (int j=0;j<ES[sx[i]].size();++j) ans[i]=min(ans[i],ES[sx[i]][j].data+query(ES[sx[i]][j].num,sy[i]));
		for (int j=0;j<ES[sy[i]].size();++j) ans[i]=min(ans[i],ES[sy[i]][j].data+query(ES[sy[i]][j].num,sx[i]));
	}
	for (int i=1;i<=n;++i)
		for (int j=0;j<ES[i].size();++j)
			for (int k=0;k<ES[i].size();++k)
				if (j!=k)
				{
					for (int t=0;t<ES[ES[i][j].num].size();++t)
						if (query3(ES[ES[i][j].num][t].num,ES[i][k].num)!=inf)
							insert(ES[ES[i][j].num][t].num,ES[i][k].num,ES[i][j].data+ES[i][k].data+ES[ES[i][j].num][t].data);
				}
	for (int i=1;i<=q;++i)
	{
		ans[i]=min(ans[i],query(sx[i],sy[i]));
		for (int j=0;j<ES[sx[i]].size();++j)
		{
			ans[i]=min(ans[i],ES[sx[i]][j].data+query2(ES[sx[i]][j].num,sy[i]));
			for (int k=0;k<ES[ES[sx[i]][j].num].size();++k) ans[i]=min(ans[i],ES[sx[i]][j].data+ES[ES[sx[i]][j].num][k].data+query2(ES[ES[sx[i]][j].num][k].num,sy[i]));
		}
		for (int j=0;j<ES[sy[i]].size();++j)
		{
			ans[i]=min(ans[i],ES[sy[i]][j].data+query2(ES[sy[i]][j].num,sx[i]));
			for (int k=0;k<ES[ES[sy[i]][j].num].size();++k) ans[i]=min(ans[i],ES[sy[i]][j].data+ES[ES[sy[i]][j].num][k].data+query2(ES[ES[sy[i]][j].num][k].num,sx[i]));
		}
	}
	for (int i=1;i<=q;++i) printf("%d\n",ans[i]==inf?-1:ans[i]);
	return 0;
}