在百字节森林（Hundred Byte Wood）中，蚂蚁们建造了 $n$ 个蚁穴，编号为 $1$ 到 $n$。这些蚁穴通过双向隧道连接，使得任意两个蚁穴之间恰好存在一条简单路径。

春天到了，蚁后宣布进行年度蚁穴结构轮换。这次轮换涉及 $m$ 只工蚁：第 $i$ 只工蚁需要在时间 $t_i$ 从其当前的蚁穴（编号为 $a_i$）出发，沿着最短路径前往编号为 $b_i$ 的蚁穴。所有蚂蚁的移动速度相同，且在到达目的地之前都不会中途停留。

蚁后怀疑在同一点聚集过多的蚂蚁可能会组织并引发分裂。对于每一只工蚁，蚁后想知道这只蚂蚁在旅途中会在某一点（隧道上的某一点或某个蚁穴中）遇到的最多其他工蚁数量是多少。注意，相遇仅发生在旅途过程中；也就是说，如果第 $i$ 只蚂蚁在时间 $t'_i$ 到达目的地，那么蚂蚁 $i$ 和蚂蚁 $j$ 仅能在时间 $t \in [t_i, t'_i] \cap [t_j, t'_j]$ 相遇。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n, m \le 100\,000$)，分别表示蚁穴的数量和参与轮换的工蚁数量。

接下来的 $n - 1$ 行描述了隧道结构。每行包含三个整数 $u_i, v_i, d_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le d_i \le 10^9$)，表示蚁穴 $u_i$ 和 $v_i$ 之间由一条双向隧道连接，工蚁通过该隧道需要 $d_i$ 个单位时间。

最后 $m$ 行描述了参与轮换的工蚁。每行包含三个整数 $a_i, b_i, t_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le t_i \le 10^9$)，含义如题目描述所述。

输出格式

输出 $m$ 行；第 $k$ 行应包含第 $k$ 只蚂蚁在旅途中同时遇到的最多其他工蚁的数量（不包括第 $k$ 只蚂蚁本身）。

样例

输入 1

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

输出 1

2
2
2
1
0