rt，大部分都是从星际导航那题复制过来的

#include<bits/stdc++.h>
#define v to[i]
#define w val[i]
using namespace std;
const int N=5e4+1,M=1e5;
int tot,head[N],nxt[M],to[M],val[M];
int n,m,q,fa[N],depth[N],f[N][16],maxv[N][16];

struct edge
{
    int x,y,z;
    bool operator <(edge o)const {
        return z<o.z;
    }
}e[M];

int read() {
    int x=0; char ch=0; while (!isdigit(ch) ) ch=getchar();
    while (isdigit(ch) ) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return x;
}
void add(int x,int y,int z) {
    to[tot]=y,val[tot]=z,nxt[tot]=head[x],head[x]=tot++;
    to[tot]=x,val[tot]=z,nxt[tot]=head[y],head[y]=tot++;
}
int find(int x) {
    return fa[x]^x?fa[x]=find(fa[x]):x;
}
bool merge(int x,int y) {
    x=find(x),y=find(y);
    fa[x]=y; return x^y;
}
void kruskal()
{
    sort(e,e+m);
    for (int i=0;i<m;i++)
        if (merge(e[i].x,e[i].y) )
            add(e[i].x,e[i].y,e[i].z);
}
void dfs(int u,int Fa) {
    for (int i=1;i<16;i++) f[u][i]=f[f[u][i-1] ][i-1],maxv[u][i]=max(maxv[u][i-1],maxv[f[u][i-1] ][i-1]);
    depth[u]=depth[Fa]+1; for (int i=head[u];~i;i=nxt[i]) if (v^Fa) f[v][0]=u,maxv[v][0]=w,dfs(v,u);
}
int LCA(int x,int y)
{
    int ans=0; if (depth[x]>depth[y]) swap(x,y); for (int i=15;~i;i--)
    if (depth[x]<=depth[f[y][i] ]) ans=max(ans,maxv[y][i]),y=f[y][i]; if (x==y) return ans;
    for (int i=15;~i;i--) if (f[x][i]^f[y][i]) ans=max(ans,max(maxv[x][i],maxv[y][i]) ),x=f[x][i],y=f[y][i];
    return max(ans,max(maxv[x][0],maxv[y][0]) );
}
void clear()
{
    tot=0;
    memset(f,0,sizeof f);
    memset(maxv,0,sizeof maxv);
    memset(depth,0,sizeof depth);
}
int main()
{
    int _=0;
    while (~scanf("%d%d",&n,&m) )
    {
        if (_++>0) putchar('\n');
        memset(head,-1,sizeof head);
        for (int i=1;i<=n;i++) fa[i]=i;
        for (int i=0;i<m;i++) e[i]={read(),read(),read()};
        q=read(); kruskal(); for (int i=1;i<=n;i++) if (!depth[i]) dfs(i,0);
        while (q--) { int x=read(),y=read(); printf("%d\n",LCA(x,y) ); }
        clear();
    }
    return 0;
}