#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int inf=1e9,N=1e6;
int n,m,q,deg[N+5],vis[N+5];
queue<int>que;
const int Mod=(1<<23);
struct Mp{
	int hd[Mod];
	int tot;
    pii e[N+5];
    int val[N+5],nxt[N+5];
    void add(int u,int v,int w){
    	if(u>v)swap(u,v);
    	int x=(1ll*u*n+1ll*v)&(Mod-1);
    	e[++tot]=make_pair(u,v),val[tot]=w,nxt[tot]=hd[x],hd[x]=tot;
	}
	int find(int u,int v){
		if(u>v)swap(u,v);
		int x=(1ll*u*n+1ll*v)&(Mod-1);
		for(int i=hd[x];i;i=nxt[i])if(e[i].fi==u&&e[i].se==v)return val[i];
		return -1;
	}
}mp,mp1;
vector<pii>road[N+5],Road[N+5];
struct Node{int to,id,w;};vector<Node>Ins[N+5];
int qs[N+5],qt[N+5],Ans[N+5],Mn[N+5];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		road[u].pb(make_pair(v,w));
		road[v].pb(make_pair(u,w));
		++deg[u],++deg[v];
		mp.add(u,v,w);
	}
	for(int i=1;i<=n;++i)if(deg[i]<=5)que.push(i);
	while(que.size()){
		int u=que.front();que.pop();if(vis[u])continue;vis[u]=1;
		for(auto v:road[u])
			if(!vis[v.fi]){
				Road[u].pb(v),--deg[v.fi];
				if(deg[v.fi]<=5)que.push(v.fi);
			}
	}
	scanf("%d",&q);
	for(int i=1;i<=q;++i){
		int valx;
		scanf("%d%d",&qs[i],&qt[i]),Ans[i]=inf,mp1.add(qs[i],qt[i],i);
		valx=mp.find(qs[i],qt[i]);if(valx>=0)Ans[i]=valx;
		for(auto v:Road[qs[i]]){
			Ins[qt[i]].pb(Node{v.fi,i,v.se}),valx=mp.find(v.fi,qt[i]);
			if(valx>=0)Ans[i]=min(Ans[i],v.se+valx);
			for(auto v1:Road[v.fi]){
		  		valx=mp.find(v1.fi,qt[i]);
		  		if(valx>=0)Ans[i]=min(Ans[i],v.se+v1.se+valx);
		    }
		}
		for(auto v:Road[qt[i]]){
			Ins[qs[i]].pb(Node{v.fi,i,v.se}),valx=mp.find(v.fi,qs[i]);
			if(valx>=0)Ans[i]=min(Ans[i],v.se+valx);
			for(auto v1:Road[v.fi]){
		  		valx=mp.find(v1.fi,qs[i]);
		  		if(valx>=0)Ans[i]=min(Ans[i],v.se+v1.se+valx);
		  	}
		}
	}
	for(int i=1;i<=n;++i)Mn[i]=inf;
	for(int i=1;i<=n;++i){
		for(auto v:road[i])
		  for(auto v1:Road[v.fi])
		    Mn[v1.fi]=min(Mn[v1.fi],v1.se+v.se);
		for(auto v:Ins[i])Ans[v.id]=min(Ans[v.id],v.w+Mn[v.to]);
		for(auto v:road[i])
		  for(auto v1:Road[v.fi])Mn[v1.fi]=inf;
		int valx;
		for(auto v:Road[i])
		  for(auto v1:Road[i]){
		  	if(v.fi==v1.fi)continue;
			valx=mp1.find(v.fi,v1.fi);
			if(valx>=0)Ans[valx]=min(Ans[valx],v.se+v1.se);
		    for(auto v2:Road[v.fi]){
		    	valx=mp1.find(v2.fi,v1.fi);
		    	if(valx>=0)Ans[valx]=min(Ans[valx],v.se+v1.se+v2.se);
			}
		  }
	}
	for(int i=1;i<=q;++i){
		if(Ans[i]>3e8)Ans[i]=-1;
		printf("%d\n",Ans[i]);
	}
	return 0;
}