题目描述

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有 $n$ 个等待点，有 $n-1$ 条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在 $n$ 个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

输入格式

第一行两个正整数 $n$ 和 $m$，分别表示等待点的个数（等待点也从 $1$ 到 $n$ 进行编号）和获奖所需要完成集合的次数。

随后 $n-1$ 行，每行两个正整数 $a,b$，表示编号为 $a$ 和编号为 $b$ 的等待点之间有一条路。

随后 $m$ 行，每行用三个正整数 $x,y,z$，表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式

输出共 $m$ 行，每行两个用空格隔开的整数 $p,c$。其中第 $i$ 行表示第 $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\%$ 的数据，$n\leq2\times10^3$，$m\leq2\times 10^3$。

对于 $100\%$ 的数据，$1\leq x,y,z\leq n\leq 5\times10^5$，$1\leq m\leq 5\times 10^5$。

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

10 10
1 2
2 3
3 4
2 5
4 6
6 7
6 8
5 9
1 10
7 7 3
2 1 3
2 6 2
9 4 3
9 1 9
9 8 3
9 4 6
3 2 7
6 6 8
8 10 3

7 3
2 2
2 3
3 4
9 3
3 6
4 5
3 4
6 1
3 6