题目描述

${N}$头牛${（2<=n<=1000）}$别人被标记为${1}$到${n，}$在同样被标记${1}$到${n}$的${n}$块土地上吃草，第${i}$头牛在第${i}$块 牧场吃草。

这${n}$块土地被${n-1}$条边连接。 奶牛可以在边上行走，第${i}$条边连接第${Ai，}$${Bi}$块牧场，第${i}$条边的长度是${Li（}$${1<=Li<=10000）}$。

这些边被安排成任意两头奶牛都可以通过这些边到达的情况，所以说这是一棵树。

这些奶牛是非常喜欢交际的，经常会去互相访问,他们想让你去帮助他们计算${Q(1<=q<=1000)}$对奶牛之间的距离。

输入格式

第一行：两个被空格隔开的整数：${N}$和${Q}$

第二行到第${n}$行：第${i+1}$行有两个被空格隔开的整数：${AI，}$${BI，}$${LI}$

第${n+1}$行到${n+Q}$行：每一行有两个空格隔开的整数：${P1，}$${P2，}$表示两头奶牛的编号。

输出格式

第${1}$行到第${Q}$行：每行输出一个数，表示那两头奶牛之间的距离。

样例

输入样例

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

输出样例

2
7