P16386 [IATI 2025] Kitten

:::align{center} Who doesn't love videos with kittens and trees? ::: Kitten Kis has found a big tree in his yard. He wants to climb it, but the tree is too big! The tree he has found has $N$ nodes and $N-1$ edges. Each edge has a positive length. We define the distance between any two nodes as the sum of the lengths of the edges on a simple path between them. Additionally, we define the diameter of a tree as the biggest distance between any two nodes. To climb the tree, Kis wants to make the tree diameter as small as possible. In order to achieve this he can do at most $K$ operations. For each operation he picks an edge in the tree that has non-zero length and then he decreases it by $1$. Kis is just a small kitten so he asks for your help. Write the program $\textbf{kitten}$ to find the smallest possible diameter that can be achieved by doing at most $K$ operations.

The first line of the standard input contains the integers $N$ and $K$. Then each of the last $N-1$ contains $3$ positive integers: $u_i \ v_i \ w_i$ describing an edge between nodes $u_i$ and $v_i$ of length $w_i$.

Output one integer -- the smallest possible diameter of the tree that can be achieved after at most $K$ operations.

### Constraints - $1 \leq N \leq 2 \times 10^5$; - $0 \leq K \leq 10^9$; - $1 \leq u_i, v_i \leq N$; - $1 \leq w_i \leq 10^4$. ### Subtasks | **Subtask** | **Points** | **Required subtasks** | **$N$** | **$K$** | **$w_i$** | | :---: | :---: | :---: | :---: | :---: | :---: | | $1$ | $5$ | $-$ | $\leq 2~000$ | $=0$ | $\leq 10^4$ | | $2$ | $5$ | $1$ | $\leq 2 \times 10^5$ | $=0$ | ^ | | $3$ | $8$ | $-$ | ^ | $=1$ | ^ | | $4$ | $22$ | $-$ | $\leq 200$ | $\leq 10^9$ | $=1$ | | $5$ | $15$ | $4$ | $\leq 2~000$ | $\leq 10^9$ | ^ | | $6$ | $15$ | $4-5$ | $\leq 2 \times 10^5$ | $\leq 10^9$ | ^ | | $7$ | $10$ | $4-6$ | $\leq 2 \times 10^5$ | $\leq 10^9$ | $(\Sigma_{i=1}^{N-1} \ w_i) \leq 10^6$ | | $8$ | $20$ | $1-7$ | ^ | ^ | $\leq 10^4$ | The points for a subtask are given only if all tests for it and the required subtasks are passed **successfully**.