Kth-path

問題文

$N$頂点の木があり、頂点は$1,2,\ldots,N$と番号付けられています。

$i(1 \leq i \leq N-1)$番目の辺は頂点$u_i$と頂点$v_i$を結び、重みは$w_i$です。

異なる頂点$u, v$に対し、頂点$u$から頂点$v$までのパスに含まれる辺の重みの総和を$dist(u,v)$とおきます。

$1 \leq u < v \leq N$を満たす全ての$(u, v)$に対する$dist(u, v)$を並べた数列を考えます。

この数列を昇順に並び替えた時、先頭から$K$番目の要素を求めてください。

制約

• $2 \leq N \leq 2 \times 10^4$
• $1 \leq u_i, v_i \leq N$
• $1 \leq w_i \leq 10^9$
• $1 \leq K \leq \frac{N(N-1)}{2}$
• 与えられるグラフは木である。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N \: K \\ u_1 \: v_1 \: w_1 \\ \vdots \\ u_{N-1} \: v_{N-1} \: w_{N-1} \\$

出力

答えを出力せよ。

サンプル1

4 5
1 2 1
2 3 2
2 4 3

4

$dist(1,2)=1, dist(1,3)=3, dist(1,4)=4, dist(2,3)=2, dist(2,4)=3, dist(3, 4)=5$となります。

これらを昇順に並び替えた時、$1,2,3,3,4,5$となるので、先頭から$5$番目の$4$を出力します。

サンプル2

12 15
7 8 200461365
1 4 142541250
10 12 932937719
2 6 913604024
6 8 942889106
3 6 997126869
8 11 861400492
8 9 329257068
1 8 64078190
5 7 214221265
9 10 927859136

743939698