#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int D=7;
const int M=N*2;
int n,m,q;
int a[N];
int hd[N],to[M],cst[M],nxt[M],ec=0,deg[N];
void _link(int u,int v,int w){ to[++ec]=v; cst[ec]=w; nxt[ec]=hd[u]; hd[u]=ec; }
void link(int u,int v,int w){ ++deg[u],++deg[v],_link(u,v,w); _link(v,u,w); }
vector<pair<int,int>> g[N];
void init(){
	queue<int> Q;
	int cnt=0;
	for(int i=1;i<=n;i++) if(deg[i]<D) Q.push(i);
	while(!Q.empty()){
		int u=Q.front(); Q.pop();
		a[u]=++cnt;
		for(int e=hd[u];e;e=nxt[e]) if(!a[to[e]]&&--deg[to[e]]==D){
			Q.push(to[e]);
		}
	}
	for(int i=1;i<=n;i++) for(int e=hd[i];e;e=nxt[e]) if(a[to[e]]>a[i]) g[i].push_back({to[e],cst[e]}); 
}
unordered_map<int,int> d3[N],d2[N],d1[N];
void upd(unordered_map<int,int>* const mp,int u,int v,int w){
	if(u==v) return;
	int& x=mp[u][v];
	if(!x) x=w;
	else x=min(x,w);
}
int qry(const unordered_map<int,int>* const mp,int u,int v){
	if(u==v) return 0;
	if(!mp[u].count(v)) return 1e9;
	else return mp[u].at(v);
}
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);
		if(u==v) continue;
		if(u>v) swap(u,v);
		link(u,v,w);
		upd(d1,u,v,w);
		upd(d2,u,v,w);
		upd(d3,u,v,w);
	}
	init();
	for(int i=1;i<=n;i++){
		for(auto [u,wu]:g[i]) for(auto [v,wv]:g[i]) if(u<v) {
			upd(d2,u,v,wu+wv);
			upd(d3,u,v,wu+wv);
		}
		for(int e=hd[i];e;e=nxt[e]){
			int ma=i,mb=to[e],we=cst[e];
			for(auto [u,wu]:g[ma]) for(auto [v,wv]:g[mb]) if(u<v&&u!=mb&&v!=ma){
				upd(d3,u,v,wu+we+wv);
			}
		}
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int s,t;
		scanf("%d%d",&s,&t);
		int ans=qry(d3,s,t);
		for(auto [u,wu]:g[s]) {
			ans=min(ans,wu+qry(d2,u,t));
			for(auto [v,wv]:g[u]){
				ans=min(ans,wu+wv+qry(d1,v,t));
			}
		}
		for(auto [v,wv]:g[t]) {
			ans=min(ans,wv+qry(d2,s,v));
			for(auto [u,wu]:g[v]) {
				ans=min(ans,wu+wv+qry(d1,s,u));
			}
		}
		printf("%d\n",ans==1e9?-1:ans);
	}
}