#1852. 「一本通 4.4 练习 1」Dis
「一本通 4.4 练习 1」Dis
题目描述
给出 个点的一棵树,多次询问两点之间的最短距离。
注意:边是双向的。
输入格式
第一行为两个整数 和 。 表示点数, 表示询问次数;
下来 行,每行三个整数 ,表示点 和点 之间存在一条边长度为 ;
再接下来 行,每行两个整数 ,表示询问点 到点 的最短距离。
输出格式
输出 行。对于每次询问,输出一行。
样例 1
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\le n\le 10^4,1\le m\le 2\times 10^4,0\lt k\le 100,1\le x,y\le n$。