채권 홍보 행진

지금은 불기 2600년이고 세계는 큰 전쟁을 치르는 중이다. 어디서나 돈과 자원이 모자라고 우리나라도 사정은 같다. 전시에 자금을 빨리 모으는 흔한 방법은 채권을 발행하는 것이다.

우리나라에는 마을이 $N$개 있고, 마을 사이는 도로로 이어져 있다. 어느 마을에서 어느 마을로든 도로를 따라 갈 수 있으며, 두 마을을 잇는 경로는 언제나 정확히 하나뿐이다.

정부는 채권을 홍보하려고 행진을 $K$번 계획했다. 행진에는 1번부터 $K$번까지 번호를 붙인다. $i$번 행진은 마을 $A_i$에서 출발해 마을 $B_i$로 간다. 마을 사람들은 이미 돈을 다 썼기 때문에 홍보는 도로 위에서만 한다. 예산이 넉넉하지 않아서 각 행진은 지나가는 도로 중 연속한 구간 하나에서만 홍보한다. 예를 들어 어떤 행진이 마을 A, B, C, D를 이 순서로 지난다고 하자. A부터 D까지 모든 도로에서 홍보해도 되고, B와 C 사이 도로에서만 홍보해도 된다. 그러나 A와 B 사이 도로에서 홍보한 뒤 B와 C 사이 도로를 건너뛰고 C와 D 사이 도로에서 다시 홍보할 수는 없다. 아무 도로에서도 홍보하지 않아도 된다.

조사 결과 $i$번 도로에서 홍보하면 채권 판매액이 $w_i$만큼 늘어난다. $w_i$는 음수일 수도 있는데, 그 도로에서 홍보하면 판매액이 오히려 줄어든다는 뜻이다.

각 행진이 올릴 수 있는 판매액의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 20$)

각 테스트 케이스는 다음 형식으로 주어진다.

• 첫째 줄에 마을의 수 $N$과 행진의 수 $K$가 주어진다. ($2 \le N \le 100{,}000$, $1 \le K \le 100{,}000$)
• 다음 $N-1$개 줄에 도로가 한 줄에 하나씩 $a_i$ $b_i$ $w_i$ 형태로 주어진다. $i$번 도로는 마을 $a_i$와 마을 $b_i$를 잇고, 이 도로에서 홍보했을 때 늘어나는 판매액이 $w_i$다. ($0 \le a_i, b_i < N$, $-10{,}000 \le w_i \le 10{,}000$)
• 다음 $K$개 줄에 행진이 출발하는 마을 $A_i$와 도착하는 마을 $B_i$가 주어진다. $A_i$와 $B_i$가 같을 수도 있으며, 이때 행진이 지나는 도로는 없다. ($0 \le A_i, B_i < N$)

각 테스트 케이스마다 $K$개 줄을 출력한다. $j$번째 줄에는 $j$번 행진이 올릴 수 있는 판매액의 최댓값을 출력한다.

첫 번째 예제 입력의 첫 테스트 케이스에서 도로망은 다음과 같다.