Building Subways


The department of progress of a city of Orbita Interconnected Advanced (OIA) has decided to address the complex construction of an underground rapid transit. The subway network, as it is called, will link zonal centers consolidation of the city, which today is connected with tram lines, following the same route as these, which will replace.

The problem is that initially budget that is account could be not enough to perform all the work. Part of the tour will continue by tram. Then a set of sections will be chosen to become subway so that the greatest distance traveled by tram from any center not modernized to the subway network is minimal. A center is considered modernized when a section of subway has one end in that center. The subway network must be done such that it link all modernized centers.

You must write a program that, given a description of the N-1 current sections of trams that connect all N centers (so that it is possible to travel between any two of them) including its length in kilometers Li, and the budget K with which the department has expressed in the same unit, calculate what will be the maximum distance mentioned above, leaving engineers determine the detailed list of sections to be built.


You receive:

  • A line with numbers N and K (2 ≤ N ≤ 200000, K ≤ 1000000000)
  • N-1 lines with Xi, Yi, Li, centers connected by the section i and its length. (1 <= Xi, Yi <= N, 1 <= Li <= 10000000).


You must output a line with a integer number representing the maximum distance traveled by tram to reach the underground.

Example input:

5 14
1 2 3
1 3 5
5 2 7
4 2 6

Example output:


Time and memory limit:

  • 1 second
  • 256MB

Problem source: COJ