Description

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$.

Input Format

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.

Output Format

For each testdata, output one line containing the answer.

2
5 2 4
1 2 2
2 3 2
1 4 2
4 5 2
7 2 0
1 2 1
1 3 5
2 4 10
2 5 1
5 6 10
5 7 5

12
33

Hint

Translated by ChatGPT 5