给定一个包含 $n$ 个顶点和 $n-1$ 条边的无向树 $T$。树的每条边都关联着一个非负整数 $x_i$。

你的任务描述非常简单。给定 $q$ 次查询。在第 $j$ 次查询中，你需要找到不在连接顶点 $a_j$ 和 $b_j$ 的简单路径上所有边关联整数集合中的最小非负整数 $y$。

输入格式

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

接下来的 $n-1$ 行，每行包含三个整数 $u_i, v_i, x_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 0 \le x_i \le 10^9$)，表示一条关联整数 $x_i$ 的边 $(u_i, v_i)$。

接下来的 $q$ 行，每行包含一对整数 $a_j, b_j$ ($1 \le a_j, b_j \le n$)，表示关于顶点 $a_j$ 和 $b_j$ 之间路径的查询。

输出格式

对于每次查询，输出一行，包含不在对应简单路径上所有边关联整数集合中的最小非负整数 $y$。

样例

输入 1

7 6
2 1 1
3 1 2
1 4 0
4 5 1
5 6 3
5 7 4
1 3
4 1
2 4
2 5
3 5
3 7

输出 1

0
1
2
2
3
3