Niuniu has arrived in a land famous for its soda to go on a trip.

There are $n$ cities in this land, connected by $n-1$ roads such that there is a path between any two cities. These cities produce sodas with many different flavors. When traveling along road $i$, Niuniu drinks $w_i$ amount of soda. Niuniu loves drinking soda, but excessive consumption is harmful to his health. Therefore, he hopes that during his trip, the average amount of soda consumed per day is as close as possible to a given positive integer $k$.

At the same time, Niuniu wants his travel plan to be as interesting as possible. He will choose a city as his starting point, and then each day travel along a road to a city he has not visited before, eventually ending his trip at some city.

Niuniu is busy drinking cola, so he wants you to help him design a travel plan that minimizes the value of $| \text{average soda consumed per day} - k |$. Please tell him this minimum value.

Input

The first line contains two positive integers $n$ and $k$.

The next $n-1$ lines each contain three positive integers $u_i, v_i, w_i$, representing a road of length $w_i$ connecting city $u_i$ and city $v_i$.

Adjacent integers on the same line are separated by a single space.

Output

A single integer representing the integer part of the minimum value of $| \text{average soda consumed per day} - k |$. That is, you should round down this minimum value and output it.

Examples

Input 1

5 21
1 2 9
1 3 27
1 4 3
1 5 12

Output 1

1

Note 1

In the graph, the path 5->1->3 is the most suitable route. The total amount of soda consumed is $27 + 12 = 39$. The average amount of soda consumed per day is $39 \div 2 = 19.5$. $| 19.5 - 21 | = 1.5$. After rounding down, we get $1$, so the answer is $1$.

Input 2

See the provided files.

Output 2

See the provided files.

Constraints

For $20\%$ of the data, $n \leq 1000$.

For another $20\%$ of the data, it is guaranteed that there is an edge between node $i$ ($1 \leq i \leq n - 1$) and node $i + 1$.

For another $20\%$ of the data, it is guaranteed that the graph is a complete binary tree rooted at 1 (in a complete binary tree, there is a road between node $i$ ($2 \leq i \leq n$) and node $\lfloor i \div 2 \rfloor$).

For another $20\%$ of the data, it is guaranteed that all nodes except node 1 are connected directly to node 1.

For $100\%$ of the data, $2 \le n \le 5 \times 10^{4}$, $0 \le w_i \le 10^{13}$, $0 \le k \le 10^{13}$.