#include<bits/stdc++.h>

#define maxn 1000005
#define INF 1e9
#define pii pair<int,int>

using namespace std;

inline long long read(){
	long long lre=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-'){
			f=-1;
		}
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		lre=(lre<<3)+(lre<<1)+(c-'0');
		c=getchar();
	}
	return lre*f;
}

struct edge{
	int head[maxn];
	int to[2*maxn],next[2*maxn],val[2*maxn];
	int e_cnt=1;
	void add(int u,int v,int w){
		to[e_cnt]=v;
		val[e_cnt]=w;
		next[e_cnt]=head[u];
		head[u]=e_cnt++;
	}
}E;

int n,m,clo=0;
int deg[maxn],tim[maxn];
//存在点度数不超过5
vector<pii> In[maxn];//tim从小到大
vector<pii> Out[maxn];//tim从大到小
queue<int> que; 

int q;
pii qry[maxn];

set<pii> st0,st1,st2;//链和八字离线方式不同 
map<pii,int> mp0,mp1,mp2; 

void show_st(set<pii> *st){
	for(pii p:*st){
		cout<<"("<<p.first<<","<<p.second<<")";
	}
	cout<<endl;
}

void add(int &x,int y){
	x=min(x,y);
}

signed main(){
	
//	freopen("1.in","r",stdin);
	
	n=read();m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		E.add(u,v,w);E.add(v,u,w);
		deg[u]++;deg[v]++;
	}
	for(int i=1;i<=n;i++){
		if(deg[i]<=5){
			que.push(i);
			tim[i]=++clo;
		} 
	}
	while(!que.empty()){
		int x=que.front();que.pop();
		for(int i=E.head[x];i;i=E.next[i]){
			int v=E.to[i];
			deg[v]--;
			if(tim[v]==0&&deg[v]<=5){
				tim[v]=++clo;
				que.push(v);
			}
		}
	}//删点，每一个点被删前邻域内不超过5个点
	//等价于给无向图定向，使每一个点的后继结点不超过5个 
	for(int u=1;u<=n;u++){
		for(int i=E.head[u];i;i=E.next[i]){
			int v=E.to[i],w=E.val[i];
			if(tim[u]<tim[v]){
				//出边(不超过5条)
				Out[u].push_back({v,w}); 
			//	printf(" %d %d %d\n",u,v,w);
			}else{
				//入边(好像没什么卯用)
				In[u].push_back({v,w});
			}
		}
	}
//	putchar('\n');
	
	q=read();
	for(int i=1;i<=q;i++){
		qry[i].first=read();qry[i].second=read();
		if(tim[qry[i].first]>tim[qry[i].second])swap(qry[i].first,qry[i].second);
		int s=qry[i].first,t=qry[i].second;
		for(pii p:Out[s]){
			st0.insert({p.first,t});
			st0.insert({t,p.first});
			st1.insert({min(t,p.first),max(t,p.first)});
		}
		for(pii p:Out[t]){
			st0.insert({s,p.first});
			st1.insert({min(s,p.first),max(s,p.first)});
		}
		st0.insert({s,t});
		st1.insert({min(s,t),max(s,t)});
		//注意是不超过3,不是恰好3条 
		st2.insert({s,t});
		st2.insert({t,s});//长短外八 
	}
	
	for(pii p:st0)mp0[p]=INF;
	for(pii p:st1)mp1[p]=INF;
	for(pii p:st2)mp2[p]=INF;
	
	pii goal;
	for(int a=1;a<=n;a++){
		//链离线(枚举a,b,c三点) 
		for(pii p1:Out[a]){
			int b=p1.first,w1=p1.second;
			for(pii p2:Out[b]){
				int c=p2.first,w2=p2.second;
				goal={a,c}; 
				if(st0.count(goal)){
					//存在问题 
					mp0[goal]=min(mp0[goal],w1+w2);
				}
			}//八字离线
			for(pii p2:Out[a]){
				int c=p2.first,w2=p2.second;
				goal={min(b,c),max(b,c)}; 
				if(st1.count(goal)){
					//存在问题 
					mp1[goal]=min(mp1[goal],w1+w2);
				}
			}//长短八字离线 
		}
		for(pii p1:In[a]){
			int b=p1.first,w1=p1.second;
			for(pii p2:Out[b]){
				int c=p2.first,w2=p2.second;
				if(c==a)continue;
				for(pii p3:Out[c]){
					int d=p3.first,w3=p3.second;
					pii goal={a,d};
					if(st2.count(goal)){
						mp2[goal]=min(mp2[goal],w1+w2+w3);
					}
				}
			}
		}
	}
	
	for(int i=1;i<=q;i++){
		int s=qry[i].first,t=qry[i].second; 
		int ans=INF;
		for(pii p:Out[s]){
			add(ans,p.second+mp0[{p.first,t}]);
			add(ans,p.second+mp0[{t,p.first}]);
			add(ans,p.second+mp1[{min(t,p.first),max(t,p.first)}]);
			for(pii p2:Out[t]){
				if(p.first==p2.first){
					add(ans,p.second+p2.second);
				}
			}
			if(p.first==t)add(ans,p.second);
		}
		for(pii p:Out[t]){
			add(ans,p.second+mp0[{s,p.first}]);
			add(ans,p.second+mp1[{min(s,p.first),max(s,p.first)}]);
		}
		add(ans,mp0[{s,t}]);
		add(ans,mp1[{min(s,t),max(s,t)}]);
		add(ans,mp2[{s,t}]);
		add(ans,mp2[{t,s}]); 
		if(ans==INF)ans=-1;
		printf("%d\n",ans);
	}
	
	return 0;
}