Minimizing Total Collection Time in a Tree

You are given a tree with n nodes where the root is node 1. Each edge in the tree has an associated weight representing the time to travel that edge. A healthcare worker starts at the root and collects information from every family. Only the leaf nodes represent households. The worker follows a fixed route: at any node u he visits its children in increasing order of their labels. In other words, when at node u he first goes to the smallest-numbered child and recursively visits its entire subtree (collecting information at every leaf in that subtree) and returns to u, then proceeds to the next child, and so on. As a result the order in which households (i.e. leaves) are visited is uniquely determined.

To save time, you are allowed to partition the ordered list of households (i.e. leaves in the DFS order) into k consecutive segments. Then, k healthcare workers will simultaneously start at the root; each worker is responsible for visiting all households in one segment (in an optimal route) and then returning to the root. The overall time taken is the maximum time among the k workers. Your task is to determine the minimum possible overall time required to collect the temperature data for all households, assuming the segmentation is chosen optimally.

Note: The optimal route for a worker covering a set of leaves is the shortest route that starts and ends at the root and visits all given leaves. In a tree, this route is exactly twice the total weight of the minimal subtree spanning the root and those leaves.

Important: If k is larger than the number of households, some workers will not be used.

inputFormat

The input begins with two integers n and k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ n), where n is the number of nodes in the tree and k is the number of healthcare workers. The next n − 1 lines each contain three integers u v w indicating that there is an undirected edge connecting nodes u and v with a travel time of w (1 ≤ w ≤ 10^4).

It is guaranteed that the given edges form a tree with node 1 as the root. When performing the DFS, the children of every node are visited in increasing order of their labels.

outputFormat

Output a single integer, which is the minimum overall time needed (i.e. the minimized maximum route time among all segments) for the collection of household temperature data.

sample

5 1
1 2 3
1 3 2
2 4 4
2 5 1

20