题目背景

Samcompu拥有大量的**"水"**资源！！

题目描述

Samcompu需要制定一个水计划。这个计划的主要目的就是为了避开老师监视的时间来水。

老师在中途会离开机房$T$次，第$i$次将会离开$tim_i$秒。Samcompu划水的时候可不是随便乱水的。他可是拥有**"水"资源的。在他的库存中有$N$个可以水的网站。Samcompu拥有一种黑科技，他可以几乎不耗任何时间在网站与网站之间跳转并且把跳转的网页的信息秒存。也就是说，Samcompu并不需要在每一次跳转的时候花费时间去浏览网页。当然，这只局限于$N$个网站之间的$N-1$个跳转方式(保证每一个网站都可以跳转到另外的所有网站)。对于第$i$种跳转方式，第$u_i$个网站到第$v_i$个网站的跳转存在一个危险程度$w_i$，这个危险值可能会造成电脑卡死，如果Samcompu不能及时处理，那么就会完美地**被老师发现。

值得一提的是，在被查水表很多次后，Samcompu总结出了一个规律：

老师走得越久，能够保证在被老师发现之前处理好电脑卡死的危险程度的上限就越高。简单来说，两者就是成正比的关系，比例系数为1。

可惜的是，Samcompu的黑科技并不稳定，在老师第$i$次离开的时候，第$K_i$个跳转方式就不可用了。

当然，每一次水都可以从任意一个网站开始，也可以从任意一个网站结束。

现在Samcompu想知道，对于第$i$次老师离开机房时，他能够有多少种不同的安全的水的方案。两种水的方案不同当且仅当这两种水的方案的第一个网站或者最后一个网站不同。

(补充说明: 一个安全的水的方案当且仅当当前是老师第$j$次离开教室时跳转的路径中不存在一个跳转方式$i$使得$tim_j \leqslant w_i$，每一次水完后不可用的跳转方式就会恢复。)

输入格式

第一行两个正整数$T$, $N$

接下来$N-1$行，每一行三个正整数$u_i$, $v_i$, $w_i$

接下来$T$行，每一行两个正整数$tim_i$, $K_i$

输出格式

$T$行，每行一个正整数表示有多少中安全的水的方案。

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

0
4
6

提示

第一次连接1和2的边不可用，当前能经过的边的危险程度需要<1，并没有合法的方案。

第二次连接1和3的边不可用，当前能经过的边的危险程度需要<2，合法的方案有 (1,2) (2,1) (3,4) (4,3) 共四种。

第三次连接3和4的边不可用，当前能经过的边的危险程度需要<3，合法的方案有 (1,2) (1,3) (2,1) (2,3) (3,1) (3,2) 共六种。

提醒:本题计算答案按照点对的方式计算.也就是说,如果起点和终点一样,则只看做同一种方案.特别的,$(x,y)$和$(y,x)\ (x \neq y)$算作两种不同的方案.

数据范围：

Subtask 1(30 pts):

$$T=1 \qquad 1 \leqslant K_i \leqslant N \leqslant 10^3 \qquad 1 \leqslant tim_i, w_i \leqslant 10^3 $$

Subtask 2(50 pts):

$$1 \leqslant T \leqslant 5*10^3 \qquad 1 \leqslant K_i \leqslant N \leqslant 10^4 \qquad 1 \leqslant tim_i, w_i \leqslant 10^3 $$

Subtask 3(20 pts):

$$1 \leqslant T \leqslant 10^4 \qquad 1 \leqslant K_i \leqslant N \leqslant 10^4 \qquad 1 \leqslant tim_i, w_i \leqslant 10^3 $$

数据保证不同的$K_i$最多只有$10^3$个。

温馨提醒：由于出题人数据比较毒瘤，所以请尽量卡常。