RT

int fa[500005][50],dep[500005],tmp[500005],lg[1000005];
struct node{
	int v,w,next;
}edge[1000005];
int head[1000005],num;
void add(int u,int v,int w){
	edge[++num].next=head[u];
	head[u]=num;
	edge[num].w=w;
	edge[num].v=v;
}
int n,m;
void dfs(int fath,int now,int wd){
	fa[now][0]=fath,dep[now]=dep[fath]+1,tmp[now]=tmp[fath]+wd;
	for(int i=0;i<=lg[dep[now]];i++){
		fa[now][i]=fa[fa[now][i-1]][i-1];
	}
	for(int i=head[now];i;i=edge[i].next){
		if(edge[i].v!=fath)dfs(now,edge[i].v,edge[i].w);
	}
}
int LCA(int x, int y) {
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])
		x=fa[x][lg[dep[x]-dep[y]]-1];
	if(x==y) return x;
	for(int k=lg[dep[x]]-1;k>=0;--k)
		if(fa[x][k]!=fa[y][k])
			x=fa[x][k],y=fa[y][k];
	return fa[x][0];
}