델타 사분면

델타 사분면은 대부분 미탐사 상태이고, 서로 싸우는 종족이 자리 잡은 위험 구역이 곳곳에 있다. 다만 행성과 행성을 잇는 중립 지대가 몇 군데 있어서, 그 경로로는 안전하게 다닐 수 있다.

중요한 정상 회담이 잡혀 있지만 의결 정족수를 채우기 전까지는 열리지 않는다. 정족수를 채우려면 델타 사분면에 흩어진 대표를 거의 다 한곳에 모아야 하고, 엔터프라이즈호가 그 지점에서 대표단을 태운다.

행성은 $N$개이고, 중립 지대를 지나는 안전한 경로 $N-1$개가 행성을 잇는다. 경로마다 지나는 데 걸리는 시간이 정해져 있고, 어느 행성에서 어느 행성으로도 갈 수 있다.

우주선 한 대가 아무 행성에서나 출발해 출발한 행성을 포함한 서로 다른 행성 $N-k$개를 방문하고 출발점으로 돌아온다. 같은 경로를 여러 번 지나도 된다. 이때 걸리는 시간의 최솟값을 구하라.

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

각 테스트 케이스의 첫 줄에는 행성의 수 $N$과 방문하지 않아도 되는 행성의 수 $k$가 주어진다. ($2 \le N \le 10\,000$, $0 \le k \le \min(N-1,\ 20)$)

다음 $N-1$개의 줄에는 각각 세 정수가 주어진다. 순서대로 경로가 잇는 두 행성의 번호와 그 경로를 지나는 데 걸리는 시간이다. 행성 번호는 $0$부터 $N-1$까지이고, 시간은 $0$ 이상 $1\,000\,000$ 이하이다. 주어지는 그래프는 항상 연결되어 있다.

각 테스트 케이스마다 필요한 최소 이동 시간을 한 줄에 하나씩 출력한다.