24115번 - 地域 (Regions) 다국어

문제

JOI 国には N 個の都市があり,1 から N の番号がついている.これらの都市は,双方向に通行可能な道 でツリー状に接続されている.すなわち,任意の 2 つの都市は道をたどって行き来が可能であり,かつそ の経路は一意である.このとき,道は N − 1 本である.

都市を,M 個の地域に分けることにした.全ての地域は 1 つ以上の都市を含み,全ての都市はちょうど 1 つの地域に含まれるようにしなければならない.また,同じ地域に含まれる任意の 2 つの都市は,その 地域に含まれない都市を通らずに道をたどって行き来が可能でなければならない.

各地域の直径の最大値 d_max ができるだけ小さくなるように地域分けをしたい.ある地域の直径とは,そ の地域に含まれる 2 つの都市間の距離の最大値である.2 つの都市間の距離とは,2 つの都市を結ぶ経路に 含まれる道路の長さの和である.地域に 1 つしか都市が含まれない時,その地域の直径は 0 とする.

道の情報と地域の数が与えられると,d_max の最小値を計算するプログラムを作成せよ.

입력

標準入力から以下の入力を読み込め.

• 1 行目には整数 N, M が空白を区切りとして書かれている.
• 続く N − 1 行には,1 行につき 1 つの道について記述している.これらの行のうちの i 行目は道 i に ついて記述しており,整数 A_i, B_i ,C_i が空白を区切りとして書かれている.

출력

標準出力に d_max の最小値を表す 1 つの整数を出力せよ.

제한

• 2 ≤ N ≤ 30, 000 都市の数
• 2 ≤ M ≤ N 地域の数
• 1 ≤ A_i < B_i ≤ N 道 i の結ぶ 2 つの都市
• 1 ≤ C_i ≤ 100 道 i の長さ

힌트