树是一个无向图，其中任意两个顶点之间由且仅由一条路径连接。给定一棵包含 $n$ 个顶点的加权树，其中 $w(i, j)$ 表示顶点 $i$ 和 $j$ 之间边的权重。考虑从顶点 $u$ 到顶点 $v$ 的简单路径 $P = (u, s_1, \dots, s_{t-1}, v)$。记路径 $P$ 上边的权重序列为 $a = (a_1, a_2, \dots, a_t)$，其中 $a_1 = w(u, s_1), a_2 = w(s_1, s_2), \dots, a_t = w(s_{t-1}, v)$。

令 $f(u, v) = \sum_{i=1}^{t} \max_{j=1 \dots i} \{a_j\}$ 为序列 $a$ 的前缀最大值之和。给定 $q$ 次查询，每次查询由两个整数 $u$ 和 $v$ 描述。对于每次查询，你需要计算 $f(u, v)$。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 2 \cdot 10^5, 1 \le q \le 10^6$)，由单个空格分隔：树的顶点数和查询次数。

接下来的 $n - 1$ 行，每行包含三个整数 $a_i, b_i$ 和 $c_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le c_i \le 10^9$)：表示第 $i$ 条边连接的两个顶点及其权重。保证给定的边构成一棵树。

接下来的 $q$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n$)：表示第 $i$ 次查询。

输出格式

输出 $q$ 行，第 $i$ 行应包含一个整数：第 $i$ 次查询的答案。

样例

样例输入 1

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

样例输出 1

7
8
6
8