Description：

给一个 $n$ 个点 $m$ 条边的无向图，多次询问 $a_i$ 到 $b_i$ 的最短路。

$1\leqslant n,m,q\leqslant 10^5,m-n\leqslant 20$

Solution：

肯定要抓住 $m-n\leqslant 20$ 这个条件，不难想到先求一棵生成树，然后想了什么用其他边去覆盖这棵树什么的，其实并没有这么麻烦，只要先随便求出一棵生成树，然后把路径分成两类：在树上的和经过非树边的，在树上的直接树剖统计即可，对于非树边，最多只有 $20$ 个，对于这些边的所有端点跑一遍 $dijkstra$ ，然后枚举每条非树边，强制让他经过这条边，用这条边两个端点的距离和加这条边的长度更新答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,q;

#define MAXN 100010

struct edges

{

	int u,v,w;

}es[MAXN];

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	e[++edgenum] = (edge){b,lin[a],c};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b],c};lin[b] = edgenum;

	return;

}

edge ve[MAXN << 1];

int vedgenum = 0;

int vlin[MAXN] = {0};

void vadd(int a,int b,int c)

{

	ve[++vedgenum] = (edge){b,vlin[a],c};vlin[a] = vedgenum;

	ve[++vedgenum] = (edge){a,vlin[b],c};vlin[b] = vedgenum;

	return;

}

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int top[MAXN],dep[MAXN],son[MAXN],siz[MAXN],fa[MAXN];

typedef long long ll;

ll len[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = vlin[k];i != 0;i = ve[i].nxt)

	{

		if(ve[i].to != fa[k])

		{

			fa[ve[i].to] = k;

			len[ve[i].to] = len[k] + ve[i].v;

			dfs1(ve[i].to,depth + 1);

			siz[k] += siz[ve[i].to];

			if(son[k] == 0 || siz[ve[i].to] > siz[son[k]])

			{

				son[k] = ve[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = vlin[k];i != 0;i = ve[i].nxt)

	{

		if(ve[i].to != fa[k] && ve[i].to != son[k])

		{

			dfs2(ve[i].to,ve[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

ll dist(int a,int b)

{

	return len[a] + len[b] - 2 * len[LCA(a,b)];

}

edges ue[30];

int tot = 0;

ll dis[30][2][MAXN];

bool v[MAXN];

void dijkstra(int s,ll d[])

{

	d[s] = 0;

	priority_queue< pair<ll,int> > q;

	q.push(make_pair(0,s));

	memset(v,false,sizeof(v));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

	{

		es[i].u = rd();es[i].v = rd();es[i].w = rd();

		add(es[i].u,es[i].v,es[i].w);

	}

	for(int i = 1;i <= n;++i)f[i] = i;

	for(int i = 1;i <= m;++i)

	{

		int p = find(es[i].u),q = find(es[i].v);

		if(p == q)

		{

			ue[++tot] = es[i];

			continue;

		}

		f[p] = q;

		vadd(es[i].u,es[i].v,es[i].w);

	}

	dfs1(1,1);dfs2(1,1);

	memset(dis,0x3f,sizeof(dis));

	for(int i = 1;i <= tot;++i)

	{

		dijkstra(ue[i].u,dis[i][0]);

		dijkstra(ue[i].v,dis[i][1]);

	}

	scanf("%d",&q);

	int a,b;

	for(int i = 1;i <= q;++i)

	{

		a = rd();b = rd();

		ll ans = dist(a,b);

		for(int k = 1;k <= tot;++k)

		{

			ll curans = min(dis[k][0][a] + ue[k].w + dis[k][1][b],dis[k][1][a] + ue[k].w + dis[k][0][b]);

			ans = min(ans,curans);

		}

		printf("%I64d\n",ans);

	}

	return 0;

}