题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

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

输出样例

2
7