给出 nn 个点的一棵树，多次询问两点之间的最短距离。
注意：
- 边是无向的。
- 所有节点的编号是 1,2,…,n1,2,…,n。
输入格式
第一行为两个整数 nn 和 mm。nn 表示点数，mm 表示询问次数；
下来 n−1n−1 行，每行三个整数 x,y,kx,y,k，表示点 xx 和点 yy 之间存在一条边长度为 kk；
再接下来 mm 行，每行两个整数 x,yx,y，表示询问点 xx 到点 yy 的最短距离。
树中结点编号从 11 到 nn。
输出格式
共 mm 行，对于每次询问，输出一行询问结果。
数据范围
2≤n≤1042≤n≤104,
1≤m≤2×1041≤m≤2×104,
0<k≤1000<k≤100,
1≤x,y≤n
样例输入
2 2
1 2 100
1 2
2 1
样例输出
100
100
提示
