Problem Description

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.

Input

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.

Output

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.

2
6 2
0 1 5
0 2 1
0 3 10
0 4 5
1 5 9
6 13
0 1 2
0 2 7
0 3 9
1 4 8
1 5 7

Case #1: 34
Case #2: 61

Hint

for case#2
we need two person to fully explore the maze with minimum cost. One go though 4->1->0->2, another go though 5->1->0->3.

Author

BJTU