The festival must go on

Cube World has $N$ cities and $N-1$ bidirectional roads. Every pair of distinct cities is joined by a route, so the road network is a tree. Cities are numbered from $1$ to $N$, roads are numbered from $1$ to $N-1$, and road $i$ has length $l_i$.

The ruler of Cube World is holding a festival. He picks $M$ of the $N-1$ roads and runs one event on each picked road, such as a car parade or a sports match. The transport ministry complained that traffic would be paralysed, so the ruler decided to keep the disruption small. Among all ways to pick $M$ roads, he takes one that minimizes the maximum length of a simple path that uses only picked roads. The length of a path is the sum of the lengths of the roads on it, and a path that stays in one city has length $0$.

For each test case, find that minimized maximum.

The first line contains an integer $T$ ($1 \le T \le 100$), the number of test cases.

The first line of each test case contains two space separated integers $N$ and $M$ ($2 \le N \le 2000$, $1 \le M \le N-1$), where $N$ is the number of cities and $M$ is the number of roads to pick. The next $N-1$ lines describe the roads. The $i$-th of them contains three space separated integers $a_i$, $b_i$, $l_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le l_i \le 10^6$), meaning that road $i$ connects city $a_i$ and city $b_i$ and its length is $l_i$.

The sum of $N$ over all test cases does not exceed $2000$.

For each test case, print one line with the maximum length of a simple path over the picked roads, for a choice of $M$ roads that makes this value as small as possible.

A simple path is a path that never repeats a city. It is a sequence of distinct cities $c_1, c_2, \dots, c_l$ such that for every $i$ with $1 \le i \le l-1$ a road connects city $c_i$ and city $c_{i+1}$. In this problem every such road has to be a picked road.