Pruning Trees

All submissions for this problem are available.
You have a tree (an acyclic, connected graph) with edge weights, but it is far too big. You are to prune the tree by deleting some edges so that the following property holds. For each connected component C of the pruned tree, there is some node r_{C} such that for every node v in C, the total weight of the edges on the path between v and r_{C} is at most some given value d.
You happen to like heavy trees so you want to delete the minimum possible total edge weight to satisfy this property.
Input
The first line of each test case is an integer T ≤ 40 indicating the number of test cases to follow. The first line of each test case contains two integers n and d that indicate there are n nodes in the tree and d is as specified in the problem description. Suppose the nodes in the tree are indexed by integers between 0 and n1. Then n1 lines follow, each containing three integers u,v, and w. This indicates that there is an edge of weight w between nodes u and v. The input will be such that the graph is connected with no cycles. No edge will be given more than once and no edge in the input will be a loop (i.e. u ≠ v for each input edge).
Bounds: 1 ≤ n ≤ 100, 0 ≤ d ≤ 10^{9}, and, for each edge u,v,w in the input, 0 ≤ u < v ≤ n1 and 1 ≤ w ≤ 10^{7}.
Output
The output for each test case consists of a single line containing a single integer denoting the maximum total weight of edges that can remain after deleting some edges so that the remaining graph satisfies the property described in the problem description.
Example
Input: 3 5 10 0 1 10 1 2 9 1 3 10 3 4 9 10 1 0 1 1 0 2 1 1 3 1 1 4 1 2 5 1 2 6 1 2 7 1 6 8 1 6 9 1 7 2 0 1 1 0 2 2 1 3 1 1 4 2 2 5 2 2 6 7 Output: 29 7 7
Author:  friggstad 
Tester:  pieguy 
Editorial  http://discuss.codechef.com/problems/PRUNING 
Tags  friggstad hard may11 
Date Added:  7012011 
Time Limit:  5 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions