4728 - 提高：倍增求 LCA:dis
时间限制 : 1 秒
内存限制 : 512 MB
给出 n 个点的一棵树，多次询问两点之间的最短距离。
注意：边是双向的。
输入
第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；
下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；
再接下来 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≤n≤10^4 ,1≤m≤2×10^4 ,0