Path in a graph is defined to be disjoint if there is no common edge and vertex that belongs to more than one path. Given a connected graph with N nodes and N − 1 weighted edges, we are interested in finding a set of up to K paths in the graph which are disjoint to each other. The set of paths should be chosen so that the sum of all weight of edges of the paths is the maximum possible. The example above shows two configurations of disjoint paths in the same graph. When the limit of paths to be drawn (K) is one (shown on the left), the maximum sum of all the weight of its edges is 13 (5+2+6). However, when we are allowed to draw up to 2 disjoint paths, we can draw two paths whose sum of edge weights evaluates to 15 (shown on the right). Input The input begins with a line containing an integer T, the number of test cases follow. Each case begins with two non-negative integers N and K (K ≤ N ≤ 60). The next N − 1 following lines each will contains three integers: A, B and D (1 ≤ A,B ≤ N; and |D| ≤ 10000) which means that there is an undirected edge from node A to node B with weight D. Output For each case, print in a single line the maximum possible sum of weight of up to K disjoint paths in the given graph. Sample Input 2 61 125 322 346 633
2/2 251 62 125 322 346 633 251 Sample Output 13 15