Delta Quadrant

Much of the Delta Quadrant is unexplored, and warring races hold many dangerous regions. A few neutral zones run from planet to planet, and travel along those is safe.

A critical summit is scheduled, but it stays on hold until a quorum of its members is present. Reaching that quorum means gathering almost every delegate in the Delta Quadrant at one location, where the Enterprise picks them up.

There are $N$ planets, and $N-1$ safe paths through neutral zones connect them. Each path takes a known amount of time to traverse, and every planet is reachable from every other planet.

A single ship leaves from any planet, visits $N-k$ distinct planets counting the one it started from, and returns to that same planet. It may traverse a path more than once. Find the shortest total time.

The first line has $T$, the number of test cases. ($1 \le T \le 50$)

Each test case begins with a line holding two integers: $N$, the number of planets, and $k$, the number of planets that need not be visited. ($2 \le N \le 10\,000$, $0 \le k \le \min(N-1,\ 20)$)

The next $N-1$ lines each hold three integers: the two planet numbers the path connects, then the time needed to traverse that path. Planets are numbered $0$ through $N-1$, and each time is between $0$ and $1\,000\,000$, inclusive. The given graph is always connected.

For each test case, print the minimum travel time on its own line.