Reducing Network Diameter

The computer network of a country forms a tree, so there is exactly one path between any two nodes. The weight $w(j,k)$ of an edge $(j,k)$ is the time a message needs to travel from node $j$ to node $k$, and $w(j,k) = w(k,j)$. The length of the path between two nodes $s$ and $t$ is the sum of the weights of the edges on that path. The diameter of a tree network is the length of the longest path between two nodes. For example, the network in Figure 1 has diameter 30, on the path between node 1 and node 6. The diameter is the largest delay any pair of nodes can suffer, so it is an important parameter of a computer network.

Figure 1. A tree network

You can shorten the communication time of an edge by paying a cost for it. Paying a cost $c$ for an edge $(j,k)$ reduces $w(j,k)$ to $\max\{w(j,k)-c,\ 0\}$, and $c$ can be any non-negative real number. Find the minimum total cost that makes the diameter of the tree network at most $D$. For the network in Figure 1 with a target diameter $D = 26$, the minimum cost is 4: pay 4 for the edge $(5,6)$ and its weight drops from 9 to 5. For $D = 0$ the minimum cost is 40, because every edge weight has to become 0. For $D = 19$ the minimum cost is 11.5, paying 3.5 for the edge $(2,3)$, 0.5 for the edge $(3,4)$, and 7.5 for the edge $(3,5)$. Write a program that computes the minimum cost for a given tree network and a target diameter $D$.

Your program reads from standard input. The first line holds the number of test cases $T$. Each test case starts with a line holding the number of nodes $n$ ($1 \le n \le 40{,}000$) and the target diameter $D$ ($0 \le D \le 50{,}000$). Each of the next $n-1$ lines holds three integers that describe one edge: the two end nodes of the edge and its weight. Every edge weight is an integer between $1$ and $50{,}000$, and node numbers are integers between $1$ and $n$. The initial weights are integers, but a cost of real value can reduce a weight to a real number.

Your program writes to standard output. For each test case, print on one line the minimum cost that makes the diameter of the tree network at most $D$. Print the value with one digit after the decimal point, rounded off from the second digit.