题目描述

$n$ 头被标记为 $1$ 到 $n$ 的牛，在同样被标记 $1$ 到 $n$ 的 $n$ 块土地上吃草，第 $i$ 头牛在第 $i$ 块牧场吃草。 这 $n$ 块土地被 $n-1$ 条边连接。 奶牛可以在边上行走，第 $i$ 条边连接第 $a_i$，$b_i$ 块牧场，第 $i$ 条边的长度是 $l_i$ 。 这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。 这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算 $q$ 对奶牛之间的距离。

输入格式

第一行：两个被空格隔开的整数：$n$ 和 $q$。

第二行到第 $n$ 行：第 $i+1$ 行有两个被空格隔开的整数：$a_i，b_i，l_i$ 。

第 $n+1$ 行到 $n+q$ 行：每一行有两个空格隔开的整数：$p_1，p_2$，表示两头奶牛的编号。

输出格式

共 $q$ 行，每行输出一个数，表示那两头奶牛之间的距离。

样例

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

2
7

数据规模与约定

对于 $100\%$ 的数据，$2\leq n\leq 1000$，$1\leq q \leq 1000$，$1\leq l_i \leq 10000$。

题目来源

资格赛