B. 世界树
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给定一棵 $$$n$$$ 个节点的无根树 $$$T$$$，节点编号为 $$$1$$$ 到 $$$n$$$，每条边有一个整数边权（可能为负）。

定义树上两点 $$$a,b$$$ 的距离 $$$\operatorname{dis}(a,b)$$$ 为它们之间的唯一简单路径上的边权之和。

现有 $$$q$$$ 次查询，每次查询给定两个节点 $$$x$$$ 和 $$$y$$$，请你计算并输出： $$$$$$ \max_{u \in T}\left(\operatorname{dis}(x,u)+\operatorname{dis}(y,u)\right) $$$$$$

Input

第一行两个整数 $$$n,q$$$ ($$$1 \le n,q \le 5 \times 10^5$$$)，分别表示树的节点数和查询次数。

接下来 $$$n-1$$$ 行，每行三个整数 $$$u,v,w$$$ ($$$1 \le u,v \le n$$$, $$$|w| \le 10^9$$$)，表示节点 $$$u$$$ 与节点 $$$v$$$ 之间有一条边权为 $$$w$$$ 的边。保证输入构成一棵树。

接下来 $$$q$$$ 行，每行两个整数 $$$x,y$$$ ($$$1 \le x,y \le n$$$)，表示一次查询。

Output

共 $$$q$$$ 行，对于每次查询，输出一行一个整数，表示所求的最大值。

Example
Input
4 3
1 2 1
2 3 2
2 4 -1
1 1
1 2
1 3
Output
6
5
3