Little L has recently become obsessed with The Legend of Zelda: Breath of the Wild and particularly enjoys the mini-challenges in the game.

There is a challenge in the game called "LCT". The rules are as follows: there is a tree with $N$ nodes, and each edge has an integer weight $v_i$. If $v_i \ge 0$, traversing this edge yields a gain of $v_i$; if $v_i < 0$, traversing this edge requires paying a toll of $-v_i$. Little L needs to control the protagonist Link to cut exactly $K$ edges in the tree, and then add $K$ edges with a weight of $0$ to obtain a new tree. Then, he will choose two nodes $p, q$ in the tree, travel along the simple path connecting these two nodes from $p$ to $q$, and pay the toll / receive the corresponding gain for every edge passed.

TemporaryDO, the god of the Hyrule continent, wants to test Link. He tells Link that if Link can cut the appropriate edges and choose the appropriate path to maximize the total gain minus the total toll, he will give him the legendary Master Sword.

Little L wants to obtain the Master Sword, so he has come to you for help. Please tell him the maximum possible value of the total gain minus the total toll that Link can obtain.

Input

The first line contains two positive integers $N$ and $K$, where $0 \le K < N \le 3 \times 10^5$.

The next $N - 1$ lines each contain three integers $x_i, y_i, v_i$, representing that the $i$-th edge connects nodes $x_i$ and $y_i$ with an edge weight of $v_i$.

Output

Output a single integer representing the answer.

Examples

Input 1

5 1
1 2 3
2 3 5
2 4 -3
4 5 6

Output 1

14

Note 1

One possible optimal strategy is: cut the edge $(2, 4, -3)$, add the edge $(3, 4, 0)$, and choose $(p, q) = (1, 5)$.

Input 2

See lct/lct2.in in the contestant directory.

Output 2

See lct/lct2.ans in the contestant directory.

Subtasks

• For 10% of the data, $k = 0$;
• For another 10% of the data, $k = 1$;
• For another 15% of the data, $k = 2$;
• For another 25% of the data, $k \le 100$;
• For the remaining data, there are no special constraints.

For all test data, it is guaranteed that $1 \le N \le 3 \times 10^5$, $1 \le x_i, y_i \le N$, and $|v_i| \le 10^6$.

Note

The problem is not difficult.