Migrated from Lutece 1437 谭松松的旅游计划

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

谭松松是一个爱旅游的人，他非常的热爱旅游，即便身体被掏空也要坚持旅游。喵哈王国由N个城市组成，由N-1条道路连通，每条道路长度为ci,使得任意两座城市都能相互到达。谭松松有M个旅游计划，每个旅游计划有一个起点ai,一个终点bi,所以谭松松想知道，对于每个旅游计划，从起点到终点的最短路长度为多少？

Input

第一行两个整数N(2≤N≤100000，)，M(1≤M≤100000)，表示城市个数，谭松松的旅游计划个数。

接下来N-1行，每行三个整数li,ri,ci（1≤ci≤10000），表示li号城市和ri号城市之间有一条长度为ci的道路。

接下来M行，每行两个整数ai,bi表示旅游计划的起点和终点。

Output

输出M行，表示每个旅游计划的最短距离。

Samples

7 6
1 2 5
1 3 4
3 7 7
2 4 4
2 5 3
5 6 2
1 2
4 7
6 3
3 2
5 4
7 6

5
20
14
9
7
21

Resources

2016 UESTC Training for Graph Theory