题目描述

给出$\red{n}$个点的一棵树，多次询问两点之间的最短距离。

注意：边是双向的。

输入格式

第一行为两个整数$\red{n}$和$\red{m}$。$\red{n}$表示点数，$\red{m}$表示询问次数；

下来$\red{n−1}$行，每行三个整数 $\red{x,y,k}$，表示点$\red{x}$和点$\red{y}$之间存在一条边长度为$\red{k}$；

再接下来$\red{m}$行，每行两个整数$\red{x,y}$，表示询问点$\red{x}$到点$\red{y}$的最短距离。

输出格式

输出$\red{m}$行。对于每次询问，输出一行。

样例

输入数据1

2 2
1 2 100
1 2
2 1

输出数据 1

100
100

输入数据 2

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

输出数据 2

10
25

提示

对于全部数据，

$\red{2≤n≤10^4}$,

$\red{1≤m≤2×10^4}$,

$\red{0<k≤100}$,

$\red{1≤x,y≤n}$