1735: 修剪苹果树

       小明家的园子里有一棵苹果树，这棵苹果树的分枝全是二分叉(没有只有一个儿子的结点)，共N个节点，树节点编号为1~N，编号为1的节点为树根，边可理解为树的分枝，这些分枝上还长着若干个苹果。现在要求修剪一些分支，保留M个分支。要求修剪后，这M个分支的苹果数量最多。
       下面示意是一颗有4个树枝的苹果树(数据对应下面的样例):

输入第1行2个数，N和M(1<=M<= N,1<N<=100)。N表示树的结点数，M表示要保留的树枝数量。

接下来N-1行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

5 2
1 2 9
1 3 8
3 4 12
3 5 12

20