#include<bits/stdc++.h>
#include <utility>

#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> st,st2;//k=2任意子问题,长短八 
map<pii,int> mp,mp2;

inline 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++){
		int& s=qry[i].first=read();int& t=qry[i].second=read();
		if(tim[s]>tim[t])swap(s,t);
		for(pii p:Out[s]){
			st.insert({p.first,t});
		}
		for(pii p:Out[t]){
			st.insert({s,p.first});
		}
		st.insert({s,t});//直接自由两点 
		st2.insert({s,t});st2.insert({t,s});//长短八 
	}
	
	for(pii p:st)mp[p]=INF;
	for(pii p:st2)mp2[p]=INF;
	
	for(pii p:st){
		//内八问题
		int s=p.first,t=p.second;
		for(pii p1:Out[s]){
			for(pii p2:Out[t]){
				if(p1.first==p2.first){
					add(mp[p],p1.second+p2.second);
				}
			}
		} 
	} 
	
	for(int x=1;x<=n;x++){
		//链上问题
		for(pii p1:Out[x]){
			int y=p1.first,w1=p1.second;
			for(pii p2:Out[y]){
				int z=p2.first,w2=p2.second;
				if(st.count({x,z})){
					add(mp[{x,z}],w1+w2);
				}
				if(st.count({z,x})){
					add(mp[{z,x}],w1+w2);
				}
			}
		} 
	}
	
	for(int a=1;a<=n;a++){
		//外八 
		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(b==c)continue;
				if(st.count({a,c}))add(mp[{a,c}],w1+w2);
				if(st.count({c,a}))add(mp[{c,a}],w1+w2);
				for(pii p3:Out[c]){
					int d=p3.first,w3=p3.second;
					if(st2.count({a,d}))add(mp2[{a,d}],w1+w2+w3);
				}
			}
		}
	}
	
	int s,t,ans;
	for(register int i=1;i<=q;++i){
		s=qry[i].first,t=qry[i].second; 
		ans=INF;
		for(pii p:Out[s]){
			add(ans,p.second+mp[{p.first,t}]);
			if(p.first==t)add(ans,p.second);
		}
		for(pii p:Out[t]){
			add(ans,p.second+mp[{s,p.first}]);
		}
		add(ans,mp[{s,t}]);add(ans,mp2[{s,t}]);add(ans,mp2[{t,s}]);
		if(ans==INF)ans=-1;
		printf("%d\n",ans);
	}
	
	return 0;
}