ISS Module Inspection Route

Jones has finally achieved his dream by joining a mission to the International Space Station (ISS). His first task is to inspect the electronic equipment in the station. The ISS is divided into \(N\) modules numbered from 1 to \(N\). The station is designed in such a way that there is exactly one simple path between any two modules (i.e. the modules form a tree).

Each corridor (edge) connecting two modules requires \(C_i\) time to inspect. Jones must plan a route starting at module 1, traversing every corridor at least once, and returning to module 1. Under normal circumstances, he would have to traverse each corridor twice. However, Jones has an option: he can don his spacesuit and jump outside the station to travel directly from any module to any other module. Each such jump takes a fixed time of \(K\), and he can perform at most \(M\) jumps.

Help Jones find the minimum total time required to complete his inspection. Formally, if there were no jumps the time would be \(2\sum_{i=1}^{N-1}{C_i}\). Using a jump, Jones can avoid retracing some paths. In particular, consider a branch of the tree ending at a leaf node (other than module 1) at a distance \(d\) from module 1. Without a jump, this branch is traversed twice (costing \(2d\)); with a jump used when finishing that branch, he saves \(d\) time but must pay an extra \(K\) time. Thus the net saving is \(d-K\) (only if positive). Since jumps can only be used for disjoint branches, the optimal strategy is to choose up to \(M\) leaves with the largest positive values of \(d-K\) to save as much time as possible.

The final answer is computed as follows:

[ \text{answer} = 2\sum_{i=1}^{N-1}{C_i} - \sum_{j=1}^{t}\Big( d_j - K \Big), \quad \text{where } t \le M \text{ and each } d_j - K > 0. ]

Input: The first line contains three integers \(N\), \(M\), and \(K\). Each of the next \(N-1\) lines contains three integers \(u\), \(v\), and \(C_i\), indicating that there is a corridor connecting modules \(u\) and \(v\), which requires \(C_i\) time to inspect.

Output: Output a single integer, the minimum total time required for Jones to complete his inspection and return to module 1.

inputFormat

The input begins with a line containing three integers (N) (the number of modules), (M) (the maximum number of jumps Jones can make), and (K) (the time cost of a single jump). Following this, there are (N-1) lines, each containing three integers (u), (v), and (C_i). Each line represents a bidirectional corridor between modules (u) and (v) with an inspection time of (C_i).

outputFormat

Output a single integer: the minimum total time required for Jones to traverse all corridors at least once and return to module 1, making optimal use of at most (M) jumps.

sample

4 1 5
1 2 3
2 3 4
3 4 5

17