One day, a donkey from the desert went to Casablanca, thinking that he had gone to Willy Wonka's chocolate factory because of being a donkey!

The donkey in our story has read the book "Charlie and the Chocolate Factory" only once and does not remember many details of the story. For this reason, he cannot distinguish between Casablanca and this factory. But the truth is that there really isn't much difference between the two! For example, both can be expressed as a range with
n
n Maidan imagined that with
n
-
1
n−1 roads are connected, so that one can travel from any square to any other square by passing a number of roads. (That is, the graph structure of squares and roads is a tree.)

In the chocolate factory, these roads are all made of chocolate and the donkey can eat the chocolate while crossing the roads. First, the donkey has tested a quantity of chocolates on each road (which are actually flowers on the pavements of Casablanca) and for each road he knows how delicious the chocolates on that road are. After collecting this information, Kher prepared a comprehensive map in which the available roads and the deliciousness of the chocolate on the bottom of each road were marked. Some of these palatability values ​​were negative, meaning that the donkey did not like the taste of chocolate. (Donkey doubts this a bit because he used to like all chocolates, but his recent studies of the writings of John Stuart Mill justify his dislike of some chocolates now.)

Now this donkey is planning a dream trip to this mysterious factory. The intended journey of the donkey starts from one of the fields and ends in one field. In this journey, the donkey travels between these two fields. (Note that according to the tree structure of the map, such a path is unique.) Everyone knows that the donkey in our story is a donkey for whom time is very important (due to work concerns) and he does not want to waste his time; So, he sets his plan in such a way that he must cross a number (which may be equal to 0) of the roads at the beginning of the route or the end of the route and eat the chocolate on the roads in between (which he does not cross those roads). That is, in other words, he chooses a consecutive section of the road to eat their chocolates, and before reaching this section and after that, he goes four shoes. The pleasure he gets from eating these chocolates is equal to the sum of their deliciousness.

Now, due to the lack of time, Donkey has come to you, one of the best programmers in the world, to ask you some questions about planning his trip. He will first give you the map of the chocolate factory and then
q
q asks you the question in this way: If he wants from the square
u
u to the square
v
v travels, what is the maximum amount of pleasure he can get from eating chocolates? (Note that this value is always non-negative, because the donkey can walk this path without eating any chocolate with 0 pleasure.)

input
In the first line, enter two natural numbers
n
n and
q
q is said to represent the number of squares in the chocolate factory (aka the real Casablanca!) and the number of donkey questions, respectively. Factory fields with natural numbers 1, 2, ... and
n
n are numbered.
1
≤
n
,
q
≤
100

000
1 ≤ n, q ≤ 100 000

Then in
n
-
1
The next n−1 line describes the map prepared by donkey; In each of these
n
-
1
n−1 rows of three numbers
u
u and
v
v and
d
d is said to represent the existence of a road between fields
u
u and
v
v with the amount of deliciousness of chocolate
d
d is

1
≤
u
,
v
≤
n
1≤u,v≤n
u
≠
v
u

=v
∣
d
∣
≤
1
0
9
∣d∣≤10
9


Then in each of
q
q Next line, two natural numbers
x
x and
y
y is said to represent the field number at both ends of the route in question.

1
≤
x
,
y
≤
n
1 ≤ x, y ≤ n

output
The output should include
q
Let q be rows, each of which contains only one number. The number in
i
The i-th line of that output should represent the answer
i
The i-th question is a donkey.

Example
Sample input
7 9
12-4
54-2
5 1 10
2 7 8
3 6 7
7 6 9
7 1
1 2
4 3
5 5
3 4
5 7
7 5
1 1
3 7
Plain text
Sample output
8
0
30
0
30
14
14
0
16   write in c++