#include <cstdio> #include <cstring> #include <queue> #include <set> #include <stack> #include <cstdlib> #include <algorithm> #include <time.h> #include <vector> #include <cmath> using namespace std; typedef long long LL; typedef pair<int,int>pii; const int N=5e4+5; const int S=1e5+1; const int INF=0x3f3f3f3f; struct Edge{ int v,w,next; }edge[N*2]; int head[N],tot,root[N],n,q; void add(int u,int v,int w){ edge[tot].v=v; edge[tot].w=w; edge[tot].next=head[u]; head[u]=tot++; } struct Node{ int l,r,v; }o[N*40]; int sz; void add(int &rt,int l,int r,int x){ o[++sz]=o[rt];rt=sz; ++o[rt].v; if(l==r)return; int m=(l+r)>>1; if(x<=m)add(o[rt].l,l,m,x); else add(o[rt].r,m+1,r,x); } int ask(int x,int y,int z,int l,int r,int k){ if(l==r)return l; int c1=o[o[x].l].v+o[o[y].l].v-2*o[o[z].l].v; int m=(l+r)>>1; if(c1>=k)ask(o[x].l,o[y].l,o[z].l,l,m,k); else ask(o[x].r,o[y].r,o[z].r,m+1,r,k-c1); } int fa[N][20],d[N]; void dfs(int u,int f,int w){ fa[u][0]=f;d[u]=d[f]+1; if(u!=1)add(root[u]=root[f],1,S,w); for(int i=head[u];~i;i=edge[i].next){ int v=edge[i].v; if(v==f)continue; dfs(v,u,edge[i].w); } } int lca(int u,int v){ if(d[u]<d[v])swap(u,v); for(int t=d[u]-d[v],i=0;t;t>>=1,++i) if(t&1)u=fa[u][i]; if(u==v)return u; for(int i=16;i>=0;--i){ if(fa[u][i]!=-1&&fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; } return fa[u][0]; } int main(){ while(~scanf("%d%d",&n,&q)){ tot=sz=0; memset(head,-1,sizeof(head)); for(int i=1;i<n;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); ++w; add(u,v,w),add(v,u,w); } memset(fa,-1,sizeof(fa)); dfs(1,0,1); for(int j=1;j<=16;++j){ for(int i=1;i<=n;++i){ if(fa[i][j-1]!=-1)fa[i][j]=fa[fa[i][j-1]][j-1]; } } while(q--){ int u,v; scanf("%d%d",&u,&v); int tp=lca(u,v); int k=o[root[u]].v+o[root[v]].v-2*o[root[tp]].v; if(k&1)k=k/2+1; else k/=2; printf("%d ",ask(root[u],root[v],root[tp],1,S,k)-1); } } return 0; }