题目描述

在一个神奇的森林里，住着三只可爱的小动物：小松鼠、小兔子和小狐狸。森林里有 $N$ 个树洞，有 $N-1$ 条小径连接着它们。每一条小径都连接某两个树洞。小动物们可以通过这些小径走遍森林的所有树洞。每次走过一条小径，都需要消耗一颗橡果。

小松鼠、小兔子和小狐狸经常想聚会，每次聚会，他们都会选择一个树洞，使得三个人到达这个树洞消耗的橡果总数最少。

由于他们计划中还会有很多次聚会，每次都选择一个地点是很烦人的事情，所以他们决定把这件事情交给你来完成。他们会提供给你森林的地图以及若干次聚会前他们所处的位置，希望你为他们的每一次聚会选择一个合适的地点。

输入格式

第一行两个正整数，$N$ 和 $M$。分别表示树洞个数和聚会次数；

后面有 $N-1$ 行，每行用两个正整数 $A$ 和 $B$ 表示编号为 $A$ 和编号为 $B$ 的树洞之间有一条小径。树洞的编号是从 $1$ 到 $N$ 的；

再后面有 $M$ 行，每行用三个正整数表示一次聚会的情况：小松鼠所在的树洞编号，小兔子所在的树洞编号以及小狐狸所在的树洞编号。

输出格式

一共有 $M$ 行，每行两个数 $P$ 和 $C$，用一个空格隔开。表示第 $i$ 次聚会的地点选择在编号为 $P$ 的树洞，总共消耗的橡果是经过 $C$ 条小径所需要的。

样例

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

数据范围

40% 的数据中，$1 ≤ N， M ≤ 2 × 10^3;$

100% 的数据中，$1 ≤ N， M ≤ 5 × 10 ^ 5。$