Given an undirected tree with $n$ vertices. Each edge $x$ has a cost $w_x$. The root of the tree is 1.

You have $m$ robots, each robot starts at root, walks through edges, finally stops at any vertex. When a robot travels through an edge $x$, you will pay $w_x$.

You need to make each edge to be visited by at least one robot (can be more than one robot).

Your goal is minimize the cost.

Input

The first line contains two integers, $n$ and $m$.

In the next $n-1$ lines, each line contains three integers, $u_i,v_i,w_i$, means an edge $(u_i,v_i)$ exists, and the cost is $w_i$.

It's guaranteed that the given graph is a tree.

Output

An integer representing the minimum cost.

Constraints

$1 \le n \le 5 \cdot 10^4$

$1 \le m \le 50$

$1 \le u_i, v_i \le n$

$1 \le w_i \le 10^9$