Maximizing Net Gain in the LCT Challenge

Link is given a tree with N nodes and N−1 edges. Each edge has an integer weight v_i. If v_i ≥ 0, walking that edge gains v_i points; if v_i < 0, it costs −v_i points to cross. In the LCT challenge, Link is allowed to remove (cut) exactly K edges from the tree and then add K new edges with weight 0 to reconnect the forest into a new tree.

After these operations, Link can choose any two nodes p and q in the new tree and traverse the unique simple path between them. For every edge on this path, if the original weight is nonnegative, its value is added to the total; if it is negative, then Link has two choices:

• if the edge was not cut, its negative weight is added (i.e. a cost is incurred), or
• if the edge is cut (and reconnected by a 0‐weight edge), then its cost is removed (i.e. it contributes 0 instead of a negative number). However, at most K negative edges along the chosen path can be canceled in this way.

Formally, for any simple path in the original tree, suppose the sum of all edge weights is S, and among the negative edges on that path, if you choose to cancel (cut) some of them (at most K in total) then the total improvement will be the sum of −v_i for those canceled edges. Link wants to maximize the overall value

\( \max\limits_{\text{path}} \Bigl\{ S + \sum_{\substack{e\ on\ path\\ e\ is\ negative\ and\ canceled}} (-v_e) \Bigr\} \)

Your task is to help Link determine the maximum possible value he can achieve.

inputFormat

The first line contains two integers N and K representing the number of nodes in the tree and the number of edges that can be cut, respectively.

Each of the following N−1 lines contains three integers u, v, and w indicating that there is an edge between nodes u and v with weight w.

It is guaranteed that the given edges form a tree.

outputFormat

Output a single integer: the maximum net gain (i.e. total rewards minus total fees) that Link can achieve.

sample

3 1
1 2 -5
2 3 10

10