Background

本题也有多种解法~

Description

村里有n栋房屋，有一些双向道路将它们连接起来。每天人们总是喜欢这样问：“如果我想从房子A到房子B多远？” 通常很难回答。但幸运的是，这个村庄的答案始终是唯一的，因为道路的建造方式是每两栋房屋之间都有一条唯一的简单路径（“简单”意味着你不能两次访问某个地方）。您的任务是回答所有这些好奇的人。

Format

Input

第一行中都有两个数字n（2 <= n <= 40000）和m（1 <= m <= 200），房屋数和查询数。接下来的n-1行每行由三个数字i，j，k隔开，并且在一个空格中隔开，这意味着存在一条连接房屋i和房屋j的道路，长度为k（0 <k <= 40000）。从1到n标记。接下来的m条线分别具有不同的整数i和j，您可以回答房屋i和房屋j之间的距离。

Output

对于每个测试用例，输出m行。每行代表查询的答案。在每个测试用例之后输出换行。

Sample 1

Input1

3 2
1 2 10
3 1 15
1 2
2 3

Output1

10
25

Sample 2

Input2

2 2
1 2 100
1 2
2 1

Output2

100
100

Limitation

1s, 1024KiB for each test case.