Problem Description
Consider a communication network consisting of N nodes numbered from 1 to N. The nodes are interconnected in such a way that the network has the shape of a rooted tree, with node 1 as the root. Node 1 wants to send a message (the same message) to each node which is a leaf in the tree (i.e. has no sons) – this operation is known as multicast. A message can only be sent from one node to one of its descendants (including the node itself). Each edge of the tree has an associated cost and the cost of sending a message from a node X to one of its descendants Y is the sum of the costs of the edges on the unique path from X to Y (if X=Y, then the cost is 0). The total cost of a multicast strategy is the sum of the costs of sending each message.
In order to reach its goal, node 1 will use the following multicast strategy: The strategy consists of K intermediate rounds. In the first round, node 1 sends an individual message to a subset of nodes S1 such that each leaf is a descendant of exactly one node X in S1 (this means that any node X in S1 is not a descendant of another node Y in S1). In round i (2<=i<=K), each node X in Si-1 sends an individual message to a subset Si,X of nodes from its subtree, such that each leaf which is a descendant of X is also a descendant of exactly one node in Si,X. The set of nodes Si is the union of the sets Si,X, for each X in Si-1. In the end, each node X in Sk must send a message to each leaf node which is a descendant of X.
Given the communication network, the cost of each edge and the number of intermediate rounds K, find the minimum total cost of a multicast strategy.
Input
The first line of input contains an integer number T, representing the number of test cases to follow. The first line of each test case contains 2 integer numbers: N (1<=N<=333) and K (1<=K<=10). The next N-1 lines contain 3 integers each: A, B and C (1<=C<=10.000), meaning that node B is a son of node A and the edge (A,B) has cost C.
Output
For each of the T test cases, in the order given in the input, print one line containing the minimum total cost of a multicast strategy having the specified properties.
Sample Input
1
6 1
1 2 10
1 3 11
2 4 21
2 5 17
3 6 7
Sample Output
66
