시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 32 MB212916841.975%

문제

Several years ago, the government of the well-known country Byteland decided to build a railway network to make public transport in the country a little bit easier. However, due to insufficient funds, the minister of the transport wanted the "network" to be as simple as possible. Hence, the following requirements needed to be met:

  • Every train connects directly two cities, there are no stops in between.
  • Every train operates in both directions (i.e., the train going from A to B goes from B to A as well) and the prices for the two directions are the same.
  • It is possible to go from every city to every other city (possibly with some changes).
  • The number of trains is the minimum possible.

Now, the railway network has been finished and the first customers can enjoy the speed and the reliability of the Byteland railway. The only problem is the issuing of tickets: When the customer travels from A to B using 42 trains, the assistant has to sum up the prices of the trains, which is really anoying. What is more, the assistant can make a mistake. To solve the problem, the director of the Byteland Railway Corporation hired you. Your task is to write a program which calculates the price of the tickets.

First, the program reads the description of the railway and the prices of the trains. Then, the program is given several queries to answer: each query is a pair of cities xi and yi and the answer is the price of the ticket from xi to yi.

입력

The first line of the input contains the integers N and Q (in this order) separated by a single space. N is the number of cities, 1 ≤ N ≤ 100 000, and Q is the number of queries, 1 ≤ Q ≤ 2 000 000 000. For simplicity, the cities are numbered by the integers 1, ..., N. The following N-1 lines describe the trains: each line contains three space-separated integers ai, bi and ci (1 ≤ ai, bi ≤ N, 0 ≤ ci ≤ 2 000 000 000) meaning that there is a train from the city ai to the city bi and its cost is ci. You may assume that the railway is correct, i.e., it really forms a tree. The following Q lines describe the queries: each line contains two integers xi and yi (1 ≤ xi, yi ≤ N, xi ≠ yi) — the cities for which we want to calculate the price of the ticket.

출력

The output should contain exactly Q lines. The i-th line should contain a single integer — the price of the ticket from xi to yi. You may assume that the price of a ticket from any city to any other city will fit into 32-bit signed integer, i.e., it will fit into int in C/C++ and into longint in Pascal.

예제 입력 1

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

예제 출력 1

5
6
11