Enchanted Lawns Quest#12982

Enchanted Lawns Quest

2 seconds
512 megabytes
Very hard

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 units in total. They had to carefully distribute this extra magic across the trails to minimize the possible diameter, while ensuring they used all units.

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

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

Input

The first line contains two integers and — 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.

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.

Output

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

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Note

Possible way to add magic in the first sample:

The first sample.

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