很经典的题了，不如说这种带有\(m-n\)很小这类限制的题的处理方法基本都如出一辙
由于图连通因此先搞个生成树出来，考虑非树边的数量很少，因此对于每组询问可以先用LCA求出两点间只经过树边的最短距离
考虑每条树边会如何影响答案，其实无非就是会经过这条树边的某个端点罢了，因此我们把非树边的端点都拿出来，称为关键点
不妨以每个关键点为原点跑一次Dijkstra，然后询问的时候枚举经过了哪个关键点中转就可以涵盖所有情况了
总复杂度\(O((m-n)\times n\log n)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=100005,INF=1e18;
int n,m,q,x[N],y[N],d[N],vis[N],used[N],dep[N],dis[N],anc[N][20];
vector <tri> G[N]; vector <pi> T[N]; vector <int> pnt,dist[50];
inline void DFS1(CI now=1,CI fa=0)
{
vis[now]=1; for (auto [to,w,id]:G[now]) if (!vis[to]) used[id]=1,DFS1(to,now);
}
inline void DFS2(CI now=1,CI fa=0)
{
anc[now][0]=fa; dep[now]=dep[fa]+1;
for (RI i=0;i<19;++i) if (anc[now][i]) anc[now][i+1]=anc[anc[now][i]][i]; else break;
for (auto [to,w]:T[now]) if (to!=fa)dis[to]=dis[now]+w,DFS2(to,now);
}
inline int getLCA(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y); RI i;
for (i=19;i>=0;--i) if (dep[anc[x][i]]>=dep[y]) x=anc[x][i];
if (x==y) return x;
for (i=19;i>=0;--i) if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
inline void Dijkstra(CI st,vector <int>& dist)
{
dist.resize(n+1); for (RI i=0;i<=n;++i) dist[i]=INF;
priority_queue <pi> hp; hp.push(pi(dist[st]=0,st));
while (!hp.empty())
{
int now=hp.top().se; hp.pop();
for (auto [to,w,id]:G[now])
if (dist[to]>dist[now]+w) hp.push(pi(-(dist[to]=dist[now]+w),to));
}
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%lld%lld",&n,&m),i=1;i<=m;++i)
scanf("%lld%lld%lld",&x[i],&y[i],&d[i]),G[x[i]].push_back({y[i],d[i],i}),G[y[i]].push_back({x[i],d[i],i});
for (DFS1(),i=1;i<=m;++i) if (used[i]) T[x[i]].push_back(pi(y[i],d[i])),T[y[i]].push_back(pi(x[i],d[i]));
for (DFS2(),i=1;i<=m;++i) if (!used[i]) pnt.push_back(x[i]),pnt.push_back(y[i]);
sort(pnt.begin(),pnt.end()); pnt.erase(unique(pnt.begin(),pnt.end()),pnt.end());
for (i=0;i<pnt.size();++i) Dijkstra(pnt[i],dist[i]);
for (scanf("%lld",&q),i=1;i<=q;++i)
{
int u,v; scanf("%lld%lld",&u,&v);
int ret=dis[u]+dis[v]-2LL*dis[getLCA(u,v)];
for (j=0;j<pnt.size();++j) ret=min(ret,dist[j][u]+dist[j][v]);
printf("%lld\n",ret);
}
return 0;
}