rt，代码如下：

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i, a, b) for(rll i = a; i <= b; i++)
#define Fdn(i, a, b) for(rll i = a; i >= b; i--)
#define int ll
#define pii pair<int, int>

using namespace std;

const int inf = 0x3f3f3f3f3f3f3f3f,mod = 1e9 + 7;
const int maxn = 1e5 + 7;

int n, m;
int _;
vector<pii> G[maxn], _G[maxn];
int dfn[maxn], dep[maxn], lca_st[18][maxn], dfn_clock, dis[maxn];
int fa[maxn], vis[maxn], _vis[maxn];
int _dis[45][maxn];
vector<int> node;

inline int Min(int x, int y) { return ((dep[x] < dep[y]) ? x : y); }
inline void dfs(int u, int f) {
	dfn[u] = ++dfn_clock, dep[u] = dep[f] + 1; lca_st[0][dfn_clock] = f;
	for(pii tmp : _G[u]) {
		int v = tmp.first, w = tmp.second;
		if(v == f) continue;
		dis[v] = dis[u] + w;
		dfs(v, u);
	}
}

inline void init() {
	F(i, 1, __lg(n))
		F(j, 1, n - (1 << i) + 1)
			lca_st[i][j] = Min(lca_st[i - 1][j], lca_st[i - 1][j + (1 << (j - 1))]);
}

inline int lca(int u, int v) {
	if(u == v) return u;
	u = dfn[u], v = dfn[v];
	if(u > v) swap(u, v);
	int d = __lg(v - u);
	return Min(lca_st[d][u + 1], lca_st[d][v - (1 << d) + 1]);
}

inline int Dis(int u, int v) { return dis[u] + dis[v] - 2 * dis[lca(u, v)]; }

inline int Find(int x) { return (x == fa[x] ? x : fa[x] = Find(fa[x])); }

int rnk[maxn];

inline void Dij() {
	int tot = 0;
	memset(_dis, 0x3f, sizeof _dis);
	for(int i : node) {
		++tot; rnk[i] = tot;
		priority_queue<pii, vector<pii>, greater<pii> > Q;
		Q.push({0, i}); _dis[tot][i] = 0;
		while(!Q.empty()) {
			pii yousa = Q.top(); Q.pop();
			int u = yousa.second;
			if(_vis[u] == tot) continue;
			_vis[u] = tot;
			for(pii tmp : G[u]) {
				int v = tmp.first, w = tmp.second;
				if(_dis[tot][u] + w < _dis[tot][v]) {
					_dis[tot][v] = _dis[tot][u] + w;
					Q.push({_dis[tot][v], v});
				}
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	F(i,1 , n) fa[i] = i;
	int u, v, w;
	F(i, 1, m) {
		cin >> u >> v >> w;
		G[u].push_back({v, w}), G[v].push_back({u, w});
		int x = Find(u), y = Find(v);
		if(x != y) {
			fa[x] = y; _G[u].push_back({v, w}), _G[v].push_back({u, w});
		} else {
			if(!vis[u]) node.push_back(u), vis[u] = 1;
			if(!vis[v]) node.push_back(v), vis[v] = 1;
		}
	}
	dfs(1, 0);
	init();
	Dij();
	cin >> _;
	int ans;
	while(_--) {
		cin >> u >> v;
		ans = Dis(u, v);
		for(int i : node) 
			ans = min(ans, _dis[rnk[i]][u] + _dis[rnk[i]][v]);
		cout << ans << '\n';
	}


	return 0;
}