You are given an undirected weighted tree consisting of N vertices.

You may delete any edges from the tree.

After deleting edges, the tree must be divided into exactly K connected components.

The cost of deleting an edge equals its weight.

Find the minimum total cost of deleted edges.

Input

The first line contains two integers N and K.

Each of the next N−1 lines contains three integers

u v w

representing an edge of weight w.

Output

Print the minimum total deletion cost.

Constraints

• 2 ≤ N ≤ 2 × 10^5
• 1 ≤ K ≤ N
• 1 ≤ w ≤ 10^9

Example

Input

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

Output

3

Explanation

Delete edges of weights 2 and 1.

The tree becomes exactly three connected components.

Total cost

2 + 1 = 3

---