处理时使用 solve(0, n) WA40，使用 solve(1, n) AC。

#include <bits/stdc++.h>
#define int long long
#define fs first
#define sc second

using namespace std;

const int maxn = 5e4 + 10;
const int maxd = 21;
const int inf = 1e9;
typedef pair<int, int> pii;

struct edge {
	int to, next;
	int cap, flow;
};

int n, m, s, t, q;
int head[maxn];
edge e[maxn << 1];
int cnt = -1;
vector<pii> tr[maxn];
int d[maxn];
int fa[maxn][maxd];
int mn[maxn][maxd];

void add_edge(int u, int v, int w) {
	e[++cnt].to = v;
	e[cnt].next = head[u];
	e[cnt].cap = w;
	e[cnt].flow = 0;
	head[u] = cnt;
}

void init() {
	for (int i = 0; i <= cnt; i++) e[i].flow = 0;
}

int dep[maxn];
int cur[maxn];

bool bfs() {
	memset(dep, -1, sizeof(dep));
	memcpy(cur, head, sizeof(cur));
	queue<int> q;
	dep[s] = 0;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; ~i; i = e[i].next) {
			int v = e[i].to;
			if (e[i].flow < e[i].cap && dep[v] == -1) {
				dep[v] = dep[u] + 1;
				q.push(v);
			}
		}
	}
	return dep[t] != -1;
}

int dfs(int u, int fl) {
	if (u == t) return fl;
	int now = fl;
	for (int i = cur[u]; ~i && now > 0; i = e[i].next) {
		cur[u] = i;
		int v = e[i].to;
		if (dep[v] == dep[u] + 1 && e[i].flow < e[i].cap) {
			int tmp = dfs(v, min(now, e[i].cap - e[i].flow));
			e[i].flow += tmp;
			e[i ^ 1].flow -= tmp;
			now -= tmp;
		}
	}
	return fl - now;
}

int ve[maxn];

int dinic() {
	int ans = 0, x;
	while (bfs()) while (x = dfs(s, inf)) ans += x;
	return ans;
}

int qwq[maxn], qaq[maxn], op, qr;

void solve(int l, int r, int de = 0) {
	if (l == r) return;
	init();
	s = ve[l], t = ve[l + 1];
	int w = dinic();
	tr[s].push_back({t, w});
	tr[t].push_back({s, w});
	op = qr = 0;
	for (int i = l; i <= r; i++) {
		if (dep[ve[i]] == -1) qwq[++op] = ve[i];
		else qaq[++qr] = ve[i];
	}
	for (int i = l; i <= r; i++) {
		if (i <= l + op - 1) ve[i] = qwq[i - l + 1];
		else ve[i] = qaq[i - l - op + 1];
	}
	int mid = l + op - 1;
	solve(l, mid, de + 1);
	solve(mid + 1, r, de + 1);
}

void dfs(int u, int f, int wg) {
	mn[u][0] = wg;
	fa[u][0] = f;
	d[u] = d[f] + 1;
	for (int i = 1; i < maxd; i++) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
		mn[u][i] = min(mn[u][i - 1], mn[fa[u][i - 1]][i - 1]);
	}
	for (pii v : tr[u]) {
		if (v.fs == f) continue;
		dfs(v.fs, u, v.sc);
	}
}

int lca(int u, int v) {
	int l;
	if (d[u] < d[v]) swap(u, v);
	while ((l = d[u] - d[v]) > 0) u = fa[u][__lg(l)];
	if (u == v) return u;
	for (int d = maxd - 1; ~d; d--) {
		if (fa[u][d] != fa[v][d]) u = fa[u][d], v = fa[v][d];
	}
	return fa[u][0];
}

int getmn(int u, int v) {
	int f = lca(u, v), l, y = inf;
	while ((l = d[u] - d[f]) > 0) {
		y = min(y, mn[u][__lg(l)]);
		u = fa[u][__lg(l)];
	}
	while ((l = d[v] - d[f]) > 0) {
		y = min(y, mn[v][__lg(l)]);
		v = fa[v][__lg(l)];
	}
	return y;
}

signed main() {
	memset(head, -1, sizeof(head));
	cin >> n >> m;
	for (int i = 1, u, v, w; i <= m; i++) {
		cin >> u >> v >> w;
		add_edge(u, v, w);
		add_edge(v, u, 0);
		add_edge(v, u, w);
		add_edge(u, v, 0);
	}
	for (int i = 0; i <= n; i++) ve[i] = i;
	solve(0, n);
	dfs(n, n + 1, inf);
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		cout << getmn(u, v) << endl;
	}
	return 0;
}