P5866 [SEERC 2018] Space Station

Jones has achieved his dream: he joined a mission to the International Space Station (ISS). He received his first task: to check whether the electronic equipment on the space station is working properly. The ISS is divided into $N$ modules, numbered from $1$ to $N$. Jones found that, to improve efficiency, the station was designed so that between any two modules there exists exactly one simple path. During a solar flare event, the bidirectional corridor connecting two modules can easily be affected by radiation. Checking the condition of a corridor $i$ requires $C_i$ time. Jones needs to find the fastest route that starts from module $1$, passes through every corridor at least once, and returns to module $1$. Besides moving through the corridors between modules, Jones can also put on a spacesuit, leave the station, and move directly from one module to any other module from the outside, but he can do this at most $M$ times. Jones assumes each such move takes a fixed time $K$.

The first line contains an integer $T$, which denotes the number of test cases. For each test case, the first line contains three integers $N, M, K \ (1 \leq N, M \leq 1000)$. The next $N-1$ lines each contain three integers $A, B, C \ (1 \leq A \leq B \leq N; 0 \leq C,K \leq 10^6)$, meaning there is a corridor between modules $A$ and $B$, and checking it takes $C$ time.

For each testdata, output one line containing the answer.

Translated by ChatGPT 5