Description

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

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

Input Format

测试数据第一行为两个整数 N 和 M（1<n≤10000, 0<m≤20000）。

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

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

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

Output Format

2 2
1 2 100
1 2
2 1

100
100

Source