問題文


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

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

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

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

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

制約


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

入力


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

出力


答えを出力せよ。

サンプル1


入力
4 5
1 2 1
2 3 2
2 4 3
出力
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

提出


Go (1.14)