2169 - 树上的距离(distance)

题目描述

给出 n 个点的一棵树,多次询问两个结点之间的最短距离。(边是双向的,也就是读入的结点没有父子之分)

两个结点之间的距离的定义是,两个结点之间的唯一简单路径边长的和。

输入

测试数据第一行为两个整数 NM1 < n≤10000, 0 < m≤20000)。

N 表示点数,M 表示询问次数。

下来 n-1 行,每行三个整数 x,y,k,表示点 x 和点 y 之间存在一条边长度为 k0 < k≤100)。

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

输出

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

样例

输入

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
来源

标签
题目参数
时间限制 2 秒
内存限制 256 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题