시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 11 3 3 37.500%

문제

The year is BE 2600 and the world is on a major war. Money and resource are much need in every part of the world and our country is one among them. A very common and fast way to gain money in the time of war is to issue financial bond.

In our country, there are N towns (2 ≤ N ≤ 100,000). Each town has roads connecting them. We can travel from any town to any town using these roads. It is guaranteed that there are exactly one route that we can travel between any pair of towns.

From a survey, we know that doing advertisement on the road i will contribute wi to the total value of bond sale (-10,000 ≤ wi ≤ 10,000). Be noted that it is possible that wi is negative, i.e., advertising on that road will decrease the total sale. We want to know the maximum value of sales

Write a program to calculate the maximum value of sales

입력

The first line of input contains a number T (1 ≤ t ≤ 20) that gives the number of test case. Each test case are given in the following format.

• The first line contains two integers N and K that represent the number of town and the number of road respectively.
• The following (N-1) lines. Each line contains three integers ai bi wi (0 ≤ ai, bi < N) that indicates that the ith road connect the town ai bi and the benefit of advertising on this road
• The following K lines. Each line contains two integers Ai Bi that represents the path of the parade.

출력

For each test case, output K lines each line gives the maximum sales of each parade.

예제 입력

2
5 4
0 1 5
0 2 -5
1 3 3
1 4 -3
0 2
4 2
2 3
3 4
2 2
0 1 5
0 1
1 0


예제 출력

0
5
8
3
5
5


힌트

For the first test case, the road is as follow