Junoh is top talent!!

Junoh got an assignment from his mentor. The problem solving system used in the assignment works like this.

1. There are $N$ problems and $N-1$ links, and each link joins two different problems. A link works in both directions.
2. Starting from any problem, you reach every other problem by following links.
3. For any two problems $A$ and $B$, exactly one route leads from $A$ to $B$.

Junoh picks any one of the $N$ problems and starts the test there. The first problem he picks counts as a bonus and is solved in 0 seconds. After solving a problem he chooses one of the links attached to it and moves to the problem on the other end. Passing a link costs the time written on that link, and the time to solve $B$ after $A$ equals the time to solve $A$ after $B$. He can never go back to a problem he has already passed.

Junoh wants to solve as many problems as this system allows. He can spend $T$ time on solving problems each day, and when a day's time runs out he continues the rest on the next day. The work may be cut at a day boundary. So if the link times along the chosen route add up to $S$, the number of days is $S$ divided by $T$, rounded up. For example, with $T = 4$ and a route whose link times are 3, 3, 3, the sum is 9, so the work splits into 4 + 4 + 1 and takes three days.

If several routes pass the maximum number of problems, Junoh takes the one that needs the fewest days. Given $N$, $T$ and the links, compute the number of days.

The first line contains the number of problems $N$ and the daily solving time $T$ ($2 \le N \le 50000$, $1 \le T \le 100000$). Each of the next $N-1$ lines contains three integers $A$, $B$, $C$ ($1 \le A, B \le N$, $1 \le C \le 1000$). $A$ and $B$ are the numbers of the two problems joined by a link, and $C$ is the time it takes to solve $B$ after $A$, or $A$ after $B$.

Print the smallest number of days Junoh needs to solve as many problems as possible.