#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;//链和八字离线方式不同 
map<pii,int> mp0,mp1; 

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(){
	
	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(make_pair(v,w)); 
			//	printf(" %d %d %d\n",u,v,w);
			}else{
				//入边(好像没什么卯用)
				In[u].push_back(make_pair(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(make_pair(p.first,t));
			st0.insert(make_pair(t,p.first));
			st1.insert(make_pair(min(t,p.first),max(t,p.first)));
		}
		for(pii p:Out[t]){
			st0.insert(make_pair(s,p.first));
			st1.insert(make_pair(min(s,p.first),max(s,p.first)));
		}
		st0.insert(make_pair(s,t));
		st1.insert(make_pair(min(s,t),max(s,t)));
		//注意是不超过3,不是恰好3条 
	}
	
	for(pii p:st0)mp0[p]=INF;
	for(pii p:st1)mp1[p]=INF;
	
	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;
				pii goal=make_pair(a,c); 
				if(st0.count(goal)){
					//存在问题 
					mp0[goal]=min(mp0[goal],w1+w2);
				}
			}
		}
		//八字离线
		for(pii p1:Out[a]){
			int b=p1.first,w1=p1.second;
			for(pii p2:Out[a]){
				int c=p2.first,w2=p2.second;
				pii goal=make_pair(min(b,c),max(b,c)); 
				if(st1.count(goal)){
					//存在问题 
					mp1[goal]=min(mp1[goal],w1+w2);
				}
			}
		} 
	}
	
	for(int i=1;i<=q;i++){
		int s=qry[i].first,t=qry[i].second; 
		int ans=INF;
		pii goal;
		for(pii p:Out[s]){
			goal=make_pair(p.first,t);
			add(ans,p.second+mp0[goal]);
			goal=make_pair(t,p.first);
			add(ans,p.second+mp0[goal]);
			goal=make_pair(min(t,p.first),max(t,p.first));
			add(ans,p.second+mp1[goal]);
		}
		for(pii p:Out[t]){
			goal=make_pair(s,p.first);
			add(ans,p.second+mp0[goal]);
			goal=make_pair(min(s,p.first),max(s,p.first));
			add(ans,p.second+mp1[goal]);
		}
		goal=make_pair(s,t);
		add(ans,mp0[goal]);
		goal=make_pair(min(s,t),max(s,t));
		add(ans,mp1[goal]);
		for(pii p:Out[s]){
			if(p.first==t){
				add(ans,p.second);
			}
		}
		//内八，特判一下
		for(pii p1:Out[s]){
			for(pii p2:Out[t]){
				if(p1.first==p2.first){
					add(ans,p1.second+p2.second);
				}
			}
		} 
		if(ans==INF)ans=-1;
		printf("%d\n",ans);
	}
	
	return 0;
}