题目描述

给定一棵 $n$ 个点的树。边有边权，有 $m$ 次询问，每次询问回答两个点 $x,y$ 之间的距离。

输入格式

第一行输入 $n,m$，代表点的个数和询问个数。

接下来 $n-1$ 行，每行三个整数 $u,v,w$ 描述一条树边。

接下来 $m$ 行，每行两个数字 $x,y$

输出格式

一共输出 $m$ 行，每行一个整数

7 5
1 2 5
1 3 6
2 4 7
3 6 5
4 5 3
2 7 11
1 7
2 3
5 7
5 6
3 7

16
11
21
26
22

样例 1 解释

数据范围

• $2\leq n\leq 10^4$
• $1\leq m\leq 2\times 10^4$
• $1\leq u,v\leq n$
• $1\leq w\leq 100$