Problem Description

City C is set to host a series of racing events. Before the races, $m$ tracks need to be constructed within the city.

City C has $n$ intersections, numbered $1, 2, \ldots, n$, and there are $n-1$ bidirectional roads suitable for constructing tracks, each connecting two intersections. The $i$-th road connects intersections $a_i$ and $b_i$ with a length of $l_i$. Using these $n-1$ roads, it is possible to travel from any intersection to any other.

A track is a set of distinct roads $e_1, e_2, \ldots, e_k$ such that one can start at a certain intersection, pass through roads $e_1, e_2, \ldots, e_k$ in order (each road once, without turning back) and reach another intersection. The length of a track is the sum of the lengths of the roads it includes. For safety reasons, each road can be used in at most one track.

The plan for track construction has not been finalized. Your task is to design a scheme for constructing tracks such that the shortest track among the $m$ tracks is as long as possible.

Input Format

The first line of the input file contains two space-separated positive integers $n$ and $m$, representing the number of intersections and the number of tracks to be constructed, respectively.

The next $n-1$ lines each contain three positive integers $a_i, b_i, l_i$, indicating that the $i$-th road suitable for constructing a track connects intersections $a_i$ and $b_i$ with a length of $l_i$. It is guaranteed that any two intersections can be reached from one another via these $n-1$ roads. Adjacent numbers in each line are separated by a space.

Output Format

The output should consist of a single line containing an integer, representing the maximum length of the shortest track among the $m$ tracks.

Sample Input and Output

Sample Input #1

7 1 
1 2 10 
1 3 5 
2 4 9 
2 5 8 
3 6 6 
3 7 7

Sample Output #1

31

Sample Input #2

9 3 
1 2 6 
2 3 3 
3 4 5 
4 5 10 
6 2 4 
7 2 9 
8 4 7 
9 4 4

Sample Output #2

15

Notes/Hints

Sample 1 Explanation

All intersections and roads suitable for constructing tracks are shown in the following diagram:

Numbers in parentheses indicate road numbers, while other numbers indicate road lengths. One track needs to be constructed. The track can be constructed through roads $3, 1, 2, 6$ (from intersection $4$ to intersection $7$), with a length of $9 + 10 + 5 + 7 = 31$, which is the maximum length among all possible schemes.

Sample 2 Explanation

All intersections and roads suitable for constructing tracks are shown in the following diagram:

Three tracks need to be constructed. The following three tracks can be constructed:
1. A track through roads $1, 6$ (from intersection $1$ to intersection $7$), with a length of $6 + 9 = 15$;
2. A track through roads $5, 2, 3, 8$ (from intersection $6$ to intersection $9$), with a length of $4 + 3 + 5 + 4 = 16$;
3. A track through roads $7, 4$ (from intersection $8$ to intersection $5$), with a length of $7 + 10 = 17$. The shortest track length is $15$, which is the maximum among all possible schemes.

Data Range and Constraints

The range and characteristics of all test data are as follows:

"Branch Limit" means that each intersection has at most 3 roads connected to it.

For all data, $2 \le n \le 5\times 10^4, \ 1 \le m \le n − 1, \ 1 \le a_i, b_i \le n, \ 1 \le l_i \le 10^4$.

见题面 Input 部分

见题面 Output 部分