在 Stubajtowy 森林中，蚂蚁们建造了 $n$ 个蚁穴，编号从 $1$ 到 $n$。蚁穴之间由双向地下道路连接，使得任意两个蚁穴之间有且仅有一条路径（不走回头路）。

蚁后下令进行一年一度的蚁穴轮换。轮换涉及 $m$ 只工蚁：第 $i$ 只工蚁需要在时刻 $t_i$ 离开其当前的蚁穴 $a_i$，前往蚁穴 $b_i$。

所有蚂蚁以相同的速度行进，且中途不停留。

人们担心，如果在路径上的某一点同时聚集了过多的行进蚂蚁，它们可能会发生分裂。在工蚁出发前，蚁后想知道对于每一只工蚁，它在旅途中同时遇到的其他行进蚂蚁的最大集合的大小是多少（即：在某条道路的某一点或某个蚁穴中同时出现）。我们仅考虑旅途中的相遇：更准确地说，如果第 $i$ 只蚂蚁在时刻 $t'_i$ 到达目的地蚁穴，那么我们仅计算蚂蚁 $i$ 和 $j$ 在时间区间 $[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$ 行描述参与轮换的蚂蚁。第 $i$ 行包含三个整数 $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$ 行。第 $i$ 行应包含蚂蚁 $i$ 在旅途中同时遇到的其他行进蚂蚁（不包括自身）的最大集合的大小。

样例

输入 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