There’s a maze with N steles. There are N-1 paths between those steles so that the maze looks like a tree. An adventure team wants to explorer all paths of the maze. They decide to air-drop some members at those steles, and then those members begin their tour to explore. It costs K dollars to drop one member. Unfortunately, there are some bandits on some paths. They will rob C dollars if a member goes through that path.
No member could pass the same path twice, calculate the minimum cost to fully explore the maze. The maze is considered fully explored if and only if all paths are explored by one of the members.
The first line of input contains only one integer T(<=100), the number of test cases.
For each case, the first line contains 2 integers, N(<=500) and K(<=1000) as described before. The following N-1 lines describe the path. Each line has 3 integers, S, E (0<=S, E<N) and C (<=1000), which S is the start point and E is the end point.
Each output should occupy one line. Each line should start with "Case #i: ", with i implying the case number. For each case, just output the minimum cost to explore all paths.