You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

C 国共有 $n$ 个城市。有 $n - 1$ 条双向道路，每条道路连接两个城市，任意两个城市之间能互相到达。为了使得交通更加便捷，C 国智囊团打算新建一条连接两个城市的道路，使得某些城市之间的最短距离能够比原来更小。现在智囊团共提出了 $m$ 个备选方案，你需要回答每个方案能够使得多少对城市的最短距离减小。

C 国的 $1$ 号城市特别重要，因此，$1$ 号城市到任意一个城市的简单路径上至多包括 $100$ 个城市。

输入格式

从标准输入读入数据。

第一行包含两个整数 $n$ 和 $m$。

接下来 $n - 1$ 行，每行包括三个整数 $u, v, w$。表示城市 $u$ 和城市 $v$ 之间已经存在一条长度为 $w$ 的道路。

接下来 $m$ 行，每行包括三个整数 $x,y,z$。描述了一个备选方案，该方案将在城市 $x$ 和城市 $y$ 之间建立一条长度为 $z$ 的道路。需要注意的是，每一种备选方案都是在原始的道路系统上添加一条道路，各备选方案之间互不影响。

输出格式

输出到标准输出。

对于每个方案，输出一行，仅包括一个整数，表示该方案能够使得多少对城市的最短距离减小。

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

3
1
0

样例 1 解释

原始道路系统当中，两两城市的最短路径如下：

• $1,2$ 号城市的最短距离为 $2$；
• $1,3$ 号城市的最短距离为 $6$；
• $1,4$ 号城市的最短距离为 $7$；
• $2,3$ 号城市的最短距离为 $4$；
• $2,4$ 号城市的最短距离为 $5$；
• $3,4$ 号城市的最短距离为 $9$。

第一个备选方案在 $(1,3)$ 号城市添加一条长度为 $1$ 的道路，将 $(1,3),(2,3),(3,4)$ 的最短距离缩短，故答案为 $3$。

第二个备选方案在 $(1,4)$ 号城市添加一条长度为 $6$ 的道路，将 $(1,4)$ 的最短距离缩短，故答案为 $1$。

第三个备选方案在 $2$ 号城市上添加了一条长度为 $1$ 的自环，没有缩短任何城市之间的最短距离，故答案为 $0$。

子任务

对于所有数据，保证 $n,m\le 2.5\times 10^5,~w\le 10^5,~1\le u,v,x,y\le 10^5,~0\le w\le 10^5,~0\le z\le 10^7$ 。保证原始道路系统一定构成一棵树，且 $1$ 号城市到任意一个城市的简单路径上至多包括 $100$ 个城市。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。