题目描述

一个简单的网络数据交换系统可以被描述成一棵带权无根树。每个叶子为用户，而非叶子节点则为服务器。连接服务器（或用户）与服务器的数据线则看做一条树边，边权可以看做这条数据线的长度。两两用户之间的一次数据交换请求都可以看做这个无根树上的一条从一个叶子到另一个叶子的路径。并且，这次数据交换请求将会激活路径上的所有服务器。对于一个服务器，如果在某一时刻有至少一条数据通过，则这个服务器是激活的，反之则是失活的。

同样地，这条请求也会激活路径上的所有数据线。比方说，下图描述了一个有 $3$ 个用户，$2$ 个服务器的系统。若存在一条 $(4,5)$ 请求，则服务器 $3$ 被激活，而服务器 $2$ 未激活；数据线 $(4, 3)$，$(3, 5)$ 被激活，$(1, 2)$，$(2, 3)$ 未被激活。

现在，你作为一个交换系统的管理员，要监控整个系统的运作状态。由于系统还未开发完全，你只能知道在每个时刻，有多少条数据交换的请求，以及登记某个被激活的服务器的编号（毕竟你一秒钟也干不了太多事）。你连续监控了一段时间。现在，你要开始整理自己的监控记录了。为了检测系统的负荷是否过重，对于每条监控记录，你要求出最坏情况下，被激活的数据线长度的和的最大值。为什么是数据线长度而不是服务器个数呢？因为出题人不喜欢单位 $1$。

输入格式

第一行两个整数 $n,m$，分别描述树的大小，以及监控记录的数量。

接下来 $n-1$ 行，每行三个整数 $u,v,w$，描述一条连接 $(u,v)$ 的权值为 $w$ 的边。

接下来 $m$ 行，每行两个整数 $d,s$ 描述一个监控记录。$d$ 表示登记的服务器的编号，$s$ 表示请求的数量。

输出格式

对于每个监控记录，输出一行一个整数，描述答案。

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

14
13
17

样例解释

对于记录 $(3, 1)$, 一种最坏情况为 $(1\to2\to3\to5)$。

对于记录 $(4, 1)$ , 一种最坏情况为 $(6\to4\to3\to5)$。

对于记录 $(2, 2)$ , 一种最坏情况为 $(6\to4\to3\to5),(1\to2\to3\to4)$。

数据规模与约定

对于 $30\%$ 的数据，$1\leq n,m\leq 100$。

另有 $20\%$ 的数据，保证所有 $d$ 相同。

另有 $20\%$ 的数据，保证树随机生成。

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$\sum w\leq 2^{32}-1$，$1\leq d\leq n$ 且保证 $d$ 不是叶子结点。