Kth-path

頂点の木があり、頂点はと番号付けられています。

番目の辺は頂点と頂点を結び、重みはです。

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

を満たす全てのに対するを並べた数列を考えます。

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

• 与えられるグラフは木である。
• 入力は全て整数である。

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

答えを出力せよ。

4 5
1 2 1
2 3 2
2 4 3

4

となります。

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

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