Description

Niuniu traveled to a country famous for producing soda.

On the map of this country, there are $n$ cities. These cities are connected by $n-1$ roads, and there is a path between any two cities. The soda produced in these cities has many different flavors. When passing through road $i$, Niuniu will drink $w_i$ amount of soda. Niuniu really likes drinking soda, but drinking too much is bad for health, so during this trip, he wants the average amount of soda he drinks per day to be 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 first choose one city as the starting point, then each day he travels along one road to a city he has never visited before, and finally he ends the trip at some city.

He is also busy drinking cola, so he wants you to help him design a travel plan that makes the value of $|P-k|$ (where $P$ is the average amount of soda drunk per day) as small as possible. Please tell him this minimum value.

Input Format

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

The next $n-1$ lines each contain three positive integers $u_i, v_i, w_i$, indicating that there is a road of length $w_i$ between city $u_i$ and city $v_i$.

Adjacent integers on the same line are separated by one space.

Output Format

Output one integer on a single line: the integer part of the minimum value, i.e., floor this minimum value and output it.

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

1

Hint

Sample Explanation

In the graph, the path $5\to1\to3$ is the most suitable route. The total amount of soda drunk is $27+12=39$, and the average amount per day is $39÷2=19.5$. Then $|19.5-21|=1.5$. After taking the floor, we get $1$, so the answer is $1$.

Constraints

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

For another $20\%$ of the data, it is guaranteed that node $i(1\le i\le n-1)$ is connected by an edge to node $i+1$.

For another $20\%$ of the data, it is guaranteed that the testdata forms a complete binary tree rooted at $1$ (in a complete binary tree, node $i(2\le i\le n)$ has a road to node $\lfloor i÷2\rfloor$).

For another $20\%$ of the data, it is guaranteed that all nodes except node $1$ have a road to node $1$.

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

Translated by ChatGPT 5