There is a kingdom consisting of $$$n$$$ cities. The cities are numbered from $$$1$$$ to $$$n$$$ (both inclusive) and there are $$$(n - 1)$$$ bidirectional roads connecting them. For each pair of cities, the residents can arrive one from another one through these roads.
The queen has recently decided to construct $$$k$$$ new factories. To avoid contamination, she requires that a city can have at most one factory.
You, as the royal designer, are appointed to arrange the construction and meanwhile, maximize the sum of distances between every two factories.
The distance between two factories is the length of the shortest path between the two cities where the two factories belong to. The length of a path is the sum of length of the edges in the path.
There is only one test case in each test file.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2\le n \le 10^5$$$, $$$2 \le k \le n$$$) indicating the number of cities and the number of new factories.
For the following $$$(n - 1)$$$ lines, the $$$i$$$-th line contains three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u \neq v$$$, $$$1 \le w \le 10^4$$$) indicating a road connecting city $$$u_i$$$ and $$$v_i$$$ and its length is $$$w_i$$$.
Output one line containing one single integer, indicating the maximum sum of distances between every two factories.
6 3 1 2 3 2 3 2 2 4 1 1 5 2 5 6 3
22
The sample test case is shown as follows.
We can choose to build factories in cities $$$3$$$, $$$4$$$ and $$$6$$$. Let $$$d(i, j)$$$ be the length of the shortest path between cities $$$i$$$ and $$$j$$$, the answer is $$$d(3, 4) + d(3, 6) + d(4, 6) = 3 + 10 + 9 = 22$$$.
