네트워크 지름 줄이기

어떤 나라의 컴퓨터 네트워크는 트리 구조다. 즉 두 노드 사이에는 경로가 정확히 하나 있다. 간선 $(j,k)$의 가중치 $w(j,k)$는 노드 $j$에서 노드 $k$로 메시지를 보내는 데 걸리는 시간이고, $w(j,k) = w(k,j)$라고 가정한다. 두 노드 $s$와 $t$ 사이 경로의 길이는 그 경로에 놓인 간선 가중치의 합이다. 트리 네트워크의 지름은 두 노드를 잇는 경로 가운데 가장 긴 것의 길이다. 예를 들어 그림 1의 네트워크는 노드 1과 노드 6을 잇는 경로 때문에 지름이 30이다. 지름은 네트워크에서 통신이 겪는 가장 큰 지연과 같으므로 컴퓨터 네트워크의 중요한 값이다.

그림 1. 트리 네트워크

이제 간선에 비용을 지불해 통신 시간을 줄일 수 있다고 하자. 간선 $(j,k)$에 비용 $c$를 지불하면 $w(j,k)$가 $\max\{w(j,k)-c,\ 0\}$으로 줄어든다. 비용 $c$로는 음이 아닌 실수를 아무거나 쓸 수 있다. 트리 네트워크의 지름이 $D$ 이하가 되게 하는 최소 비용을 구하려 한다. 그림 1의 네트워크에서 목표 지름이 $D = 26$이면 최소 비용은 4다. 간선 $(5,6)$에 비용 4를 지불해 가중치 9를 5로 줄이면 된다. $D = 0$이면 모든 간선의 가중치를 0으로 만들어야 하므로 최소 비용은 40이다. $D = 19$이면 간선 $(2,3)$에 3.5, 간선 $(3,4)$에 0.5, 간선 $(3,5)$에 7.5를 지불해 최소 비용이 11.5가 된다. 트리 네트워크와 목표 지름 $D$가 주어질 때 최소 비용을 구하는 프로그램을 작성하라.

입력은 표준 입력으로 주어진다. 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 노드 수 $n$ ($1 \le n \le 40{,}000$)과 목표 지름 $D$ ($0 \le D \le 50{,}000$)가 주어진다. 이어지는 $n-1$개 줄에는 간선 하나를 나타내는 정수 세 개가 주어진다. 앞의 두 정수는 간선의 두 끝 노드이고, 세 번째 정수는 간선의 가중치다. 각 간선의 가중치는 $1$ 이상 $50{,}000$ 이하의 정수이고, 노드 번호는 $1$ 이상 $n$ 이하의 정수다. 처음 가중치는 정수로 주어지지만, 실수 비용을 지불해 가중치를 실수로 줄일 수 있다.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 트리 네트워크의 지름을 $D$ 이하로 만드는 최소 비용을 한 줄에 출력한다. 소수점 아래 둘째 자리에서 반올림해 소수점 아래 첫째 자리까지 출력한다.