题目描述

给定一棵 $n$ 个顶点的带权树。记 $w(u,v)$ 为顶点 $u,v$ 之间边的权值。

考虑从顶点 $u$ 到顶点 $v$ 的唯一简单路径：

$P=(u,s_1,s_2,\ldots,s_{k-1},v)$。

按从 $u$ 走向 $v$ 的顺序，把路径上的边权记为：

$a=(a_1,a_2,\ldots,a_k)$，

其中 $a_1=w(u,s_1)$，$a_2=w(s_1,s_2)$，……，$a_k=w(s_{k-1},v)$。

定义：

$\displaystyle f(u,v)=\sum_{i=1}^{k}\max_{1\le j\le i}a_j$。

也就是说，从 $u$ 向 $v$ 行走时，每经过一条边，都记录“到目前为止遇到的最大边权”，并把这些前缀最大值全部相加。

现在有 $q$ 个询问。每个询问给出两个顶点 $(u_i,v_i)$，你需要计算 $f(u_i,v_i)$。

注意 $f(u,v)$ 一般不等于 $f(v,u)$。

当 $u=v$ 时，路径不含边，答案为 $0$。

输入格式

第一行包含两个整数 $n,q$：

• $1\le n\le2\cdot10^5$；
• $1\le q\le10^5$。

接下来 $n-1$ 行，每行包含三个整数 $a_i,b_i,c_i$：

• $1\le a_i,b_i\le n$；
• $a_i\ne b_i$；
• $1\le c_i\le10^9$。

表示顶点 $a_i$ 与 $b_i$ 之间有一条权值为 $c_i$ 的边。保证这些边构成一棵树。

接下来 $q$ 行，每行包含两个整数 $u_i,v_i$，表示一个询问。

输出格式

输出 $q$ 行。

第 $i$ 行输出一个整数 $f(u_i,v_i)$。

样例

5 4
3 1 2
3 5 8
3 4 7
5 2 1
2 1
1 2
4 5
5 5

17
18
15
0

样例说明

对于询问 $2\to1$，路径边权依次为 $(1,8,2)$，前缀最大值依次为 $(1,8,8)$，因此答案为 $1+8+8=17$。

对于询问 $1\to2$，边权依次为 $(2,8,1)$，前缀最大值为 $(2,8,8)$，答案为 $18$。

对于询问 $4\to5$，边权依次为 $(7,8)$，答案为 $7+8=15$。

子任务