Завдання зачарованих галявин

Обмеження: 2 сек., 512 МіБ

У Далекій-Далекій країні Шрек і Віслюк заблукали в Зачарованому Лісі, з’єднаному магічною мережею зачарованих стежок, що звиваються через чарівні галявини. Галявини пов’язані стежками, причому кожна стежка має значення магічного опору. Цей опір визначає, наскільки складно подорожувати вздовж даної стежки.

Між кожною парою галявин існує рівно один маршрут, утворюючи структуру, відому як дерево. У цій мережі найскладніший маршрут (відомий як діаметр дерева) визначається як максимальна можлива сума опорів уздовж будь-якого простого маршруту між двома галявинами.

Як завжди, у Віслюка з’явилася ідея. "Шреку, а що, якщо ми додамо трохи магії до цих стежок?" Шрек, завжди готовий до нових викликів, погодився, але знав, що вони мають обмежений запас магічної енергії — рівно \(w\) одиниць. Їм потрібно було обережно розподілити цю додаткову магію між стежками, щоб мінімізувати можливий діаметр, забезпечуючи при цьому використання всіх \(w\) одиниць.

Нехай \(a_i\) представляє початкове значення опору \(i\)-ї стежки, тоді потрібно знайти нові значення \(b_i\), такі що:

• \(b_i \ge a_i\),

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

• кожен \(b_i\) є цілим числом, оскільки магія може застосовуватися лише в цілих одиницях,

• діаметр мережі зачарованих галявин (найскладніший маршрут між будь-якими двома галявинами) мінімізується після коригувань.

Чи можете ви допомогти їм знайти найкращий спосіб розподілити магію?

Вхідні дані

У першому рядку задано два цілих числа \(n\) та \(w\) — кількість галявин та кількість магічної енергії, яку потрібно розподілити.

У наступних \(n-1\) рядках знаходиться по три цілі числа \(v_i\), \(u_i\) та \(a_i\) — вони позначають, що між галявинами \(v_i\) й \(u_i\) є стежка з магічним опором \(a_i\).

Вихідні дані

Виведіть одне ціле число — мінімально можливий діаметр після розподілення \(w\) очок магічної енергії.

Обмеження

\(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\),

Стежки формують дерево.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 7 1 2 2 1 3 4 1 4 5 3 5 2	14

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
2 7 1 2 4	11

Примітки

У першому прикладі магічну енергію очки можна розподілити так:

У другому прикладі, єдиним можливим розподілом є додавання 7 очок магічної енергії до єдиного ребра.