Track Construction

City C is going to host a series of car races. Before the races, $m$ tracks need to be built in the city.

City C has a total of $n$ intersections, numbered $1, 2, \dots, n$. There are $n-1$ bidirectional roads suitable for building tracks, each connecting two intersections. Specifically, the $i$-th road connects intersections $a_i$ and $b_i$ and has a length of $l_i$. With these $n-1$ roads, it is possible to travel from any intersection to any other intersection.

A track is a set of distinct roads $e_1, e_2, \dots, e_k$ such that one can start from an intersection and travel through these roads in sequence $e_1, e_2, \dots, e_k$ (without making U-turns) to reach another intersection. The length of a track is the sum of the lengths of the roads it passes through. To ensure safety, each road can be used by at most one track.

The plan for building the tracks is not yet finalized. Your task is to design a construction plan such that the minimum length among the $m$ built tracks is maximized (i.e., make the shortest track among the $m$ tracks as long as possible).

Input

The input file is named track.in.

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

The next $n-1$ lines each contain three integers $a_i, b_i, l_i$, representing the two intersections connected by the $i$-th road and its length. It is guaranteed that any two intersections can reach each other via these $n-1$ roads. There is a space between adjacent numbers in each line.

Output

The output file is named track.out.

The output contains a single integer, representing the maximum possible value of the minimum track length.

Examples

Input 1

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

Output 1

31

Note 1

The intersections and the roads suitable for building tracks are shown in the figure below:

The numbers in parentheses represent the road ID, and the numbers outside the parentheses represent the road length.

To build 1 track, one can build a track passing through roads 3, 1, 2, and 6 (from intersection 4 to intersection 7). The length of this track is $9 + 10 + 5 + 7 = 31$, which is the maximum value among all possible plans.

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

Output 2

15

Note 2

The intersections and the roads suitable for building tracks are shown in the figure below:

To build 3 tracks, one can build the following 3 tracks: 1. The track passing through roads 1 and 6 (from intersection 1 to intersection 7), with a length of $6 + 9 = 15$; 2. The track passing through roads 5, 2, 3, and 8 (from intersection 6 to intersection 9), with a length of $4 + 3 + 5 + 4 = 16$; 3. The track passing through roads 7 and 4 (from intersection 8 to intersection 5), with a length of $7 + 10 = 17$.

The minimum track length is 15, which is the maximum value among all possible plans.

Input 3

(See track/track3.in in the contestant directory)

Output 3

(See track/track3.ans in the contestant directory)

Constraints

The ranges and properties of all test data are shown in the table below:

Where "Degree $\le 3$" means that each intersection is connected to at most 3 roads.

For all data, $2 \le n \le 50,000$, $1 \le m \le n-1$, $1 \le a_i, b_i \le n$, $1 \le l_i \le 10,000$.