Dis

题目描述

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

注意：边是双向的。

输入描述

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

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

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

数据范围与提示：

对于全部数据，$2 \leq n \leq 10^4,1 \leq m \leq2 \times 10^4,0 \lt k \leq 100,1 \leq x,y \leq n $。

输出描述

输出m行。对于每次询问，输出一行。