Description

There is a tree with $n$ nodes, and each edge has a weight. You are given a positive integer $k$ in $0 \sim n$. You need to choose $k$ nodes and color them black, and color the remaining $n - k$ nodes white. After coloring all nodes, you gain a profit equal to the sum of pairwise distances among black nodes plus the sum of pairwise distances among white nodes. What is the maximum possible profit?

Input Format

The first line contains two integers $n, k$.

Lines $2$ to $n$ each contain three positive integers $u, v, w$, indicating that there is an edge $(u, v)$ of length $w$ in the tree. The input guarantees that all nodes are connected.

Output Format

Output a single positive integer, the maximum profit.

3 1
1 2 1
1 3 2

3

Hint

For $100\%$ of the testdata, $0 \leq n, k \leq 2000$.

Translated by ChatGPT 5