牛妹的苹果树
题号：NC205089
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛妹种了一棵苹果树。

这棵苹果树有n个节点，n-1条边，每一条边都有一个权值w_i。

我们定义：这棵树上的两点之间距离dist(u,v)为它们简单路径上所有边的权值和。

现在，牛妹想给你q次询问，每次询问一个区间[l,r]，求。

输入描述:

第一行，读入n和q。
接下来n-1行，每行读入u，v和w，表示一条边。
接下来q行，每行读入l和r，表示一组询问。

输出描述:

对于每一组询问，输出对应的最大距离值。
示例1

输入

复制 
3 3
1 2 20
2 3 40
1 1
1 3
1 2

输出

复制 
0
60
20

说明

第一组询问，最长距离是节点1到节点1，距离为0；
第二组询问，最长距离是节点1到节点3，距离为20+40=60；
第三组询问，最长距离是节点1到节点2，距离为20.

备注:

数据保证。