题目描述

Kumii 所在的 $M$ 城的地图可以看作是一棵树。具有 $N$ 个节点，$N - 1$ 条边。经过一条边需要花费 $W_i$ 的油量。Kumii 所在的位置是 $1$ 号节点，也就是这棵树的根。因为 Kumii 十分聪明且对偶像非常了解，所以她会沿着最短路径去找偶像。

Kumii 找到偶像后，她并不会原路返回——因为偶像并不想和她一起走，偶像转身就跑（在这之前，偶像并不会移动，数据保证偶像初始不在根节点），于是她将要开车追赶偶像。偶像会移动到位置 $P$，但 Kumii 开的太慢了以至于 Kumii 不能跟上偶像，Kumii 很慌只好开始四处乱找（随机游走）。那么问题来了，Kumii 想请求学 OI 的你帮她计算她从出发到找到偶像所消耗的期望油量是多少。

因为 Kumii 每天都朝思暮想着偶像，所以 Kumii 每天都会从 $1$ 号节点出发去寻找偶像。而偶像每天会在不同的地方，所以请你对于 $Q$ 组询问输出答案。

Kumii：偶像 mthq 最强辣！偶像是我的呀！

输入格式

第 $1$ 行两个整数 $N$，$Q$。
第 $2$ 至 $N$ 行每行三个正整数数 $m1$，$m2$，$w$ 代表 $m1$，$m2$ 节点间有一条权值为 $w$ 的边。
第 $N + 1$ 至 $N + Q$ 行 对于每组询问两个正整数 $P1$，$P2$ 。代表偶像最开始在 $P1$ 节点，被找到后会移动到 $P2$ 号节点（数据保证 $P1\neq P2$ ）

输出格式

$Q$ 行，每行一个正整数期望油量 $S$。

因为 $S$ 过大，所以请输出答案 $S\bmod (10^9+7)$ 的值。

样例

input

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

output

13
22

数据范围与提示

对于 $ 30\% $ 的数据，树是一条链，$N$ 与 $N+1$ 连边。
对于 $ 20\% $ 的数据，是一棵二叉树。
对于 $ 15\% $ 的数据，$W=1$。
数据保证对于 $ 100\% $ 的数据， $N,Q \leq 2\times 10^5$，$W \leq 10^6 $。