You are given a tree with $N$ nodes, where each edge has a weight. You are also given an integer $K$ such that $0 \le K \le N$. You need to choose $K$ nodes in the tree 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 the distances between all pairs of black nodes plus the sum of the distances between all pairs of white nodes. What is the maximum possible profit?

Input

The first line contains two integers $N$ and $K$. Each of the next $N-1$ lines contains three positive integers $fr$, $to$, and $dis$, representing an edge between $fr$ and $to$ with length $dis$. It is guaranteed that the tree is connected.

Output

Output a single positive integer representing the maximum profit.

Examples

Input 1

3 1
1 2 1
1 3 2

Output 1

3

Input 2

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

Output 2

17

Note

In the second example, coloring nodes 1 and 2 black yields the maximum profit.

Constraints

For 30% of the data, $N \le 20$. For 50% of the data, $N \le 100$. For 100% of the data, $0 \le K \le N$.