#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define rep(i,n) for(int i=1;i<=n;i++)

#define REP(i,s,t) for(int i=s;i<=t;i++)

#define clr(x,c) memset(x,c,sizeof(x))

#define op() clr(head,0);pt=edges;

#define adde(u,v) add(u,v),add(v,u)

#define qwq(x) for(edge *o=head[x];o;o=o->next)

int read(){

	int x=0;char c=getchar();bool f=true;

	while(!isdigit(c)) {

		if(c=='-') f=false;c=getchar();

	}

	while(isdigit(c)) x=x*10+c-'0',c=getchar();

	return f?x:-x;

}

const int nmax=500005;

const int inf=0x7f7f7f7f;

struct edge{

	int to;edge *next;

};

edge edges[nmax<<2],*pt,*head[nmax];

int size[nmax],fa[nmax],son[nmax],dep[nmax],id[nmax],idx[nmax],tp[nmax];

void add(int u,int v){

	pt->to=v;pt->next=head[u];head[u]=pt++;

}

void dfs(int x){

	size[x]=1;

	qwq(x) if(o->to!=fa[x]){

		int to=o->to;fa[to]=x;dep[to]=dep[x]+1;

		dfs(to);size[x]+=size[to];

		if(!son[x]||size[to]>size[son[x]]) son[x]=to;

	}

}

void DFS(int x,int top){

	id[++id[0]]=x;idx[x]=id[0];tp[x]=top;

	if(son[x]) DFS(son[x],top);

	qwq(x) if(!idx[o->to]) DFS(o->to,o->to);

}

int lca(int a,int b){

	while(tp[a]!=tp[b]){

		if(dep[tp[a]]>dep[tp[b]]) swap(a,b);

		b=fa[tp[b]];

	}

	return dep[a]>dep[b]?b:a;

}

int getdist(int a,int b){

	int ans=0;

	while(tp[a]!=tp[b]){

		if(dep[tp[a]]>dep[tp[b]]) swap(a,b);

		ans+=idx[b]-idx[tp[b]]+1;b=fa[tp[b]];

	}

	return dep[a]>dep[b]?ans+idx[a]-idx[b]:ans+idx[b]-idx[a];

}

struct node{

	int ans,res;

	node(int ans,int res):ans(ans),res(res){}

};

node qsum(int a,int b,int c){

	int la=lca(a,b),lb=lca(b,c),lc=lca(c,a),ans;

	if(la==lb) ans=lc;

	else if(la==lc) ans=lb;

	else ans=la;

	int res=getdist(a,ans)+getdist(b,ans)+getdist(c,ans);

	return node(ans,res);

}

int main(){

	op();

	int n=read(),m=read();

	rep(i,n-1){

		int u=read(),v=read();adde(u,v);

	}

	clr(son,0);clr(idx,0);id[0]=0;dep[1]=0;

	dfs(1);DFS(1,1);

	/*rep(i,n) printf("%d:%d %d %d %d %d %d \n",i,fa[i],son[i],size[i],dep[i],idx[i],tp[i]);*/

	rep(i,m){

		int u=read(),v=read(),d=read();node oo=qsum(u,v,d);

		printf("%d %d\n",oo.ans,oo.res);

	}

	return 0;

}

Y岛风景美丽宜人，气候温和，物产丰富。Y岛上有N个城市，有N-1条城市间的道路连接着它们。每一条道路都连接某两个城市。幸运的是，小可可通过这些道路可以走遍Y岛的所有城市。神奇的是，乘车经过每条道路所需要的费用都是一样的。小可可，小卡卡和小YY经常想聚会，每次聚会，他们都会选择一个城市，使得3个人到达这个城市的总费用最小。 由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。他们会提供给你地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。

第一行两个正整数，N和M。分别表示城市个数和聚会次数。后面有N-1行，每行用两个正整数A和B表示编号为A和编号为B的城市之间有一条路。城市的编号是从1到N的。再后面有M行，每行用三个正整数表示一次聚会的情况：小可可所在的城市编号，小卡卡所在的城市编号以及小YY所在的城市编号。

一共有M行，每行两个数Pos和Cost，用一个空格隔开。表示第i次聚会的地点选择在编号为Pos的城市，总共的费用是经过Cost条道路所花费的费用。

6 4
1 2
2 3
2 4
4 5
5 6
4 5 6
6 3 1
2 4 4
6 6 6

5 2
2 5
4 1
6 0

数据范围：
100%的数据中，N<=500000，M<=500000。
40%的数据中N<=2000，M<=2000。

 

Day1