模板
每次随便找2个点跑最小割，然后把割开的2部分内部单独跑
把最小割作为树上2点相连边权，注意每次都是对原图跑最小割
2点间最小割就是树上路径中边权最小值
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<22|5;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ib==ob)?EOF:*ib++;
}
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define re register
#define cs const
#define ll long long
#define pb push_back
#define poly vector<int>
#define pii pair<int,int>
#define fi first
#define se second
inline void chemx(ll &a,ll b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
cs int N=505,M=1505;
int n,m,id[N],id1[N],id2[N];
int fa[N][10],mn[N][10],dep[N];
vector<pii> e[N];
inline void add(int u,int v,int w){
e[u].pb(pii(v,w)),e[v].pb(pii(u,w));
}
void dfs(int u){
for(int i=1;i<=9;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 &x:e[u]){
int v=x.fi;
if(v==fa[u][0])continue;
fa[v][0]=u,mn[v][0]=x.se;
dep[v]=dep[u]+1,dfs(v);
}
}
inline int query(int u,int v){
int res=1e9;
if(dep[u]<dep[v])swap(u,v);
for(int i=9;~i;i--)if(dep[fa[u][i]]>=dep[v])chemn(res,mn[u][i]),u=fa[u][i];
if(u==v)return res;
for(int i=9;~i;i--)
if(fa[u][i]!=fa[v][i])chemn(res,mn[u][i]),chemn(res,mn[v][i]),u=fa[u][i],v=fa[v][i];
chemn(res,mn[v][0]),chemn(res,mn[u][0]);return res;
}
namespace Dinic{
int str,des;
int adj[N],nxt[M<<1],to[M<<1],cap[M<<1],cnt=1;
inline void addedge(int u,int v,int w){
nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v,cap[cnt]=w;
nxt[++cnt]=adj[v],adj[v]=cnt,to[cnt]=u,cap[cnt]=w;
}
int tp[N],lev[N],vis[N],tim;
queue<int> q;
inline bool bfs(){
memset(lev,-1,sizeof(lev));
q.push(str),lev[str]=0;
while(!q.empty()){
int u=q.front();q.pop();
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(cap[e]>0&&lev[v]==-1){
lev[v]=lev[u]+1,q.push(v);
}
}
}
return lev[des]!=-1;
}
inline int dfs(int u,int flow){
int res=0;
if(!flow||u==des)return flow;
for(int &e=tp[u];e;e=nxt[e]){
int v=to[e];
if(lev[v]==lev[u]+1&&cap[e]>0){
int now=dfs(v,min(flow-res,cap[e]));
cap[e]-=now,cap[e^1]+=now,res+=now;
if(flow==res)break;
}
}
return res;
}
inline int dinic(int s,int t){
str=s,des=t;int res=0;
while(bfs()){
memcpy(tp,adj,sizeof(adj));
res+=dfs(str,1e9);
}
return res;
}
inline void reset(){
for(int i=2;i<=cnt;i+=2)cap[i]=cap[i^1]=(cap[i]+cap[i^1])/2;
}
void dfs(int u){
vis[u]=tim;
for(int e=adj[u];e;e=nxt[e]){
int v=to[e];
if(cap[e]>0&&vis[v]!=tim)dfs(v);
}
}
inline void build(int l,int r){
if(l>=r)return;
int cnt1=l,cnt2=r;
reset();
int res=dinic(id[l],id[l+1]);
assert(id[l]!=id[l+1]);
add(id[l],id[l+1],res);
tim++,dfs(id[l]);
for(int i=l;i<=r;i++)
if(vis[id[i]]==tim)id1[cnt1++]=id[i];
else id1[cnt2--]=id[i];
for(int i=l;i<=r;i++)id[i]=id1[i];
build(l,cnt1-1),build(cnt2+1,r);
}
}
int main(){
memset(mn,127,sizeof(mn));
n=read(),m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
Dinic::addedge(u,v,w);
}
for(int i=1;i<=n;i++)id[i]=i;
Dinic::build(1,n);
dep[1]=1;dfs(1);
int q=read();
while(q--){
int u=read(),v=read();
cout<<query(u,v)<<'
';
}
}