충전기 K대 최소 반경

문제

전기차 충전소 운영사는 N개의 거점을 N-1개의 도로로 이어 만든 트리 모양의 도로망에 충전기를 설치하려 한다. 거점은 1번부터 N번까지 번호가 붙어 있고, 각 도로는 두 거점을 잇는 양방향 도로이며 길이는 양의 정수이다. 두 거점 사이의 거리는 둘을 잇는 유일한 경로에 놓인 도로 길이의 합이다. 충전기는 거점에만 설치할 수 있으며 한 거점에는 많아야 하나만 설치한다. 운영사는 충전기를 최대 K대까지 설치할 수 있다. 모든 거점은 가장 가까운 충전기가 설치된 거점까지의 거리가 R 이하여야 한다. 충전기가 설치된 거점 자신까지의 거리는 0이다. 충전기를 K대 이하로 설치하여 이 조건을 만족시킬 수 있는 정수 R 중 가장 작은 값을 구하시오. K 가 N 이면 모든 거점에 설치할 수 있으므로 답은 0이다. 충전기를 최소 한 대는 반드시 설치해야 하고, 도로망은 항상 모든 거점이 연결된 트리이다.

입력

첫 줄에 N 과 K 가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 15000, 1 ≤ K ≤ N 이다. 이어서 N-1개의 줄에 도로의 양 끝 거점 번호 u, v 와 길이 w (1 ≤ w ≤ 10^6)가 주어진다. 모든 값은 정수이다.

출력

조건을 만족하는 가장 작은 정수 R 을 한 줄에 출력한다.

5 2
1 2 1
2 3 1
3 4 1
4 5 1

1

1 1

0

4 2
1 2 5
1 3 7
1 4 2

5

출처: Devin.KR 자체 제작