Drawing

In 2010, the "Moțoc" kindergarten held an unusual chalk drawing contest in Iași. Each participant had to create a beautiful drawing, but was allowed to lift the chalk off the ground and resume drawing elsewhere only a limited number of times.

Sixteen years later, inspired by that contest, one of the children who took part in it came up with the following problem idea:

A tree is a connected undirected graph without cycles, having $N$ vertices and exactly $N - 1$ edges. A weighted tree, with $N$ vertices labeled from $1$ to $N$, needs to be drawn.

The weight of each edge $e$, which is a value $w(e)$, represents the exact amount of chalk consumed to trace the edge $e$.

A drawing of the tree is a way to traverse the tree with a piece of chalk such that every edge is traversed at least once. During the drawing, we are allowed to:

• retrace edges, meaning that we can traverse them multiple times; each time we traverse an edge, we consume the same amount of chalk;
• lift the chalk at most $K$ times, relocating it, after each lift, from its current vertex to any other vertex in the tree (lifting and relocating the chalk is instantaneous and costs nothing).

Note: Placing the chalk on the tree for the very first time at the beginning of the drawing does not count as a lift.

The cost of a drawing is the total amount of chalk used, which is calculated as $\sum_{e \in E} w(e) \cdot t(e)$, where $E$ is the set of edges and $t(e) \geq 1$ is the number of times edge $e$ is traversed during the entire drawing process.

Task

Given a weighted tree with $N$ vertices and an integer $K$, determine the minimum cost of a drawing of the tree that uses at most $K$ chalk lifts.

Input data

The first line of the input contains two space-separated integers $N$ and $K$, representing the number of vertices and the maximum number of chalk lifts allowed.

The following $N - 1$ lines contain three space-separated integers $u$, $v$, and $w$, meaning there is an undirected edge of weight $w$ connecting vertices $u$ and $v$.

Output data

The first line of the output must contain a single integer, representing the minimum cost of the drawing.

Constraints and clarifications

• $0 \leq K < N \leq 2 \cdot 10^5$
• $1 \leq w(e) \leq 10^6$ for any edge
• The given graph is guaranteed to be a valid tree.

Example 1

stdin

7 0
1 2 5
2 3 5
1 4 5
4 5 5
1 6 5
6 7 5

stdout

40

Explanation

With $K = 0$, the drawing must be a single continuous traversal of the tree.
A valid optimal drawing is: $3 \to 2 \to 1 \to 4 \to 5 \to 4 \to 1 \to 6 \to 7$.
There are 2 retraced edges: ([$1$,$4$] and [$4$,$5$]).

Example 2

stdin

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

stdout

30

Explanation

With $K = 1$, one pen lift is allowed.
An optimal choice is tracing: $3 \to 2 \to 1 \to 4 \to 5$, followed by lifting the chalk and relocating it to vertex $1$, then tracing $1 \to 6 \to 7$.