Enchanted Lawns Quest

Limits: 2 sec., 512 MiB

In the land of Far Far Away, Shrek and Donkey found themselves wandering through the Enchanted Forest, connected by a mystical network of enchanted trails winding through magical lawns. Lawns are linked by trails, with each trail carrying a magical resistance value. This resistance determines how difficult it is to travel along a given trail.

There is exactly one route between each pair of lawns, forming a structure known as a tree. In this network, the hardest path (known as the diameter of the tree) is defined as the maximum possible sum of resistances along any simple route between two lawns.

As usual, Donkey had an idea. "Shrek, what if we added a bit of magic to these trails?". Shrek, always ready for a new challenge, agreed but knew they had a limited supply of magical energy — exactly \(w\) units in total. They had to carefully distribute this extra magic across the trails to minimize the possible diameter, while ensuring they used all \(w\) units.

Let \(a_i\) represent the initial resistance value of \(i\)-th trail, then they needed to find new values \(b_i\) such that:

• \(b_i \ge a_i\),

• \(\sum b_i = w + \sum a_i\),

• each \(b_i\) is an integer, since magic can only be applied in whole units,

• the diameter of the enchanted lawns network (the hardest route between any two lawns) is minimized after the adjustments.

Can you help them determine the best way to spread the magic?

Input

The first line contains two integers \(n\) and \(w\) — number of lawns and amount of magic energy to distribute.

The next \(n-1\) lines contain three integers \(v_i\), \(u_i\) and \(a_i\) each — there is a trail between lawns \(v_i\) and \(u_i\) with a magical resistance value \(a_i\).

Output

Print a single integer — the minimum possible diameter after distributing \(w\) units of magical energy.

Constraints

\(2 \le n \le 2 \cdot 10^5\),

\(1 \le w \le 10^{12}\),

\(1 \le u_i, v_i \le n\),

\(1 \le a_i \le 10^7\),

all trails form a tree.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 7 1 2 2 1 3 4 1 4 5 3 5 2	14

Input (stdin) сopy	Output (stdout) сopy
2 7 1 2 4	11

Notes

Possible way to add magic in the first sample:

In the second sample, you have to add 7 to a single edge.