当前没有测试数据。

【例题1】树上距离

题目描述

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

输入格式

第一行为两个整数$n$和$m$。

$n$表示点数，$m$表示询问次数；

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

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

输出格式

输出$m$行。对于每次询问，输出一行一个整数表示答案。

数据范围与提示

对于$100\%$的数据，$2 \leq n \leq 10^{4}$，$1 \leq m \leq 2 \times 10^{4}$，$0 < k \leq 100$，$1 \leq x,y \leq n$。

样例

2 2 
1 2 100 
1 2 
2 1

100
100

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

10
25