#include<bits/stdc++.h>
#define ll long long
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
const int MAXN=1e6+5,inf=1e9;
struct Edge { int v,w; };
inline void chkmin(int &x,const int &y) { x=y<x?y:x; }
int n,m,q,ans[MAXN],dg[MAXN],rk[MAXN];
vector <Edge> G[MAXN],rE[MAXN],E[MAXN];
vector <array<int,2>> Q[MAXN];
__gnu_pbds::gp_hash_table <ll,int> D;
int qry(int u,int v) {
	if(u==v) return 0;
	ll p=1ll*min(u,v)*MAXN+max(u,v);
	int s=(D.find(p)!=D.end()?D[p]:inf);
	if(rk[u]>rk[v]) swap(u,v);
	for(auto e1:E[u]) {
		if(v==e1.v) chkmin(s,e1.w);
		for(auto e2:E[e1.v]) if(e2.v==v) chkmin(s,e1.w+e2.w);
		for(auto e2:E[v]) if(e1.v==e2.v) chkmin(s,e1.w+e2.w);
	}
	return s;
}
int stk[MAXN],tp,f[MAXN];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;++i) cin>>u>>v>>w,G[u].push_back({v,w}),G[v].push_back({u,w});
	queue <int> qu;
	for(int i=1;i<=n;++i) if((dg[i]=G[i].size())<6) qu.push(i),dg[i]=-1;
	for(int i=1;i<=n;++i) {
		int u=qu.front(); rk[u]=i,qu.pop();
		for(auto e:G[u]) if(~dg[e.v]&&(--dg[e.v]<6)) qu.push(e.v);
	}
	for(int u=1;u<=n;++u) for(auto e:G[u]) (rk[e.v]>rk[u]?E:rE)[u].push_back(e);
	for(int u=1;u<=n;++u) for(auto e1:G[u]) for(auto e2:G[u]) if(e1.v<e2.v) {
		ll p=1ll*e1.v*MAXN+e2.v;
		if(D.find(p)==D.end()) D[p]=e1.w+e2.w;
		else chkmin(D[p],e1.w+e2.w);
	}
	cin>>q;
	for(int i=1,u,v;i<=q;++i) {
		cin>>u>>v,ans[i]=inf;
		chkmin(ans[i],qry(u,v));
		for(auto e:E[u]) chkmin(ans[i],e.w+qry(e.v,v));
		for(auto e:E[v]) chkmin(ans[i],e.w+qry(u,e.v));
		Q[u].push_back({v,i}),Q[v].push_back({u,i});
	}
	fill(f+1,f+n+1,inf);
	for(int u=1;u<=n;++u) {
		for(auto e1:rE[u]) for(auto e2:E[e1.v]) for(auto e3:E[e2.v]) {
			if(f[e3.v]==inf) stk[++tp]=e3.v;
			chkmin(f[e3.v],e1.w+e2.w+e3.w);
		}
		for(auto o:Q[u]) chkmin(ans[o[1]],f[o[0]]);
		while(tp) f[stk[tp--]]=inf;
	}
	for(int i=1;i<=q;++i) cout<<(ans[i]==inf?-1:ans[i])<<"\n";
	return 0;
}