Newspapers

A city has n intersections joined by n-1 two-way streets. Using only these streets you can travel from any intersection to any other one.

Mirek delivers newspapers in this city. Every street has a known number of residents, and that number is also the number of newspapers he has to deliver on that street. Each day he picks two intersections and visits every house on the shortest route between them. His daily pay is proportional to the average number of newspapers delivered per street, that is, the number of delivered newspapers divided by the number of streets he walks.

At first Mirek picked a route made of the single street with the most residents. His boss noticed and added one rule, because too many people were getting no newspaper: the route has to use at least k streets.

Find the largest average number of newspapers delivered per street over all routes that use at least k streets.

The first line has two integers n and k ($1 \le n \le 50000$, $1 \le k \le n-1$). n is the number of intersections and k is the smallest number of streets a route may use.

Each of the next n-1 lines describes one street with three integers a, b and c ($1 \le a < b \le n$, $0 \le c \le 10^6$), meaning a street joins intersections a and b and c people live on it.

You may assume that a route using k streets exists.

Print the largest average number of newspapers delivered per street, with exactly eight digits after the decimal point. Round half up at the ninth decimal digit.