E1. Деление весов (простая версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Простая и сложная версии на самом деле являются разными задачами, поэтому прочитайте условия обеих задач внимательно.

Вам задано взвешенное корневое дерево, вершина $$$1$$$ — корень этого дерева.

Дерево — это связный граф без циклов. У корневого дерева есть специальная вершина, называемая корнем. Предком вершины $$$v$$$ называется последняя отличная от $$$v$$$ вершина на пути от корня к вершине $$$v$$$. Потомками вершины $$$v$$$ называются все вершины, для которых $$$v$$$ является предком. Вершина называется листом, если у нее нет потомков. Взвешенное дерево — это такое дерево, в котором у каждого ребра есть некоторый вес.

Вес пути — это сумма весов всех ребер на этом пути. Вес пути от вершины до самой себя равен $$$0$$$.

Вы можете совершить последовательность из нуля или более ходов. В течение одного хода вы можете выбрать ребро и поделить его вес на $$$2$$$ с округлением вниз. Более формально, в течение одного хода вы выбираете какое-то ребро $$$i$$$ и делите его вес на $$$2$$$ с округлением вниз ($$$w_i := \left\lfloor\frac{w_i}{2}\right\rfloor$$$).

Ваша задача — найти минимальное количество ходов, необходимых для того, чтобы сделать сумму весов путей от корня до каждого листа не превосходящей $$$S$$$. Другими словами, если $$$w(i, j)$$$ — это вес пути от вершины $$$i$$$ до вершины $$$j$$$, то вам необходимо сделать $$$\sum\limits_{v \in leaves} w(root, v) \le S$$$, где $$$leaves$$$ — это список всех листьев.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.

Входные данные

Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.

Первая строка набора тестовых данных содержит два целых числа $$$n$$$ и $$$S$$$ ($$$2 \le n \le 10^5; 1 \le S \le 10^{16}$$$) — количество вершин в дереве и максимально возможная сумма весов, которую вы можете получить. Следующая $$$n-1$$$ строка описывает ребра дерева. Ребро $$$i$$$ описывается тремя целыми числами $$$v_i$$$, $$$u_i$$$ и $$$w_i$$$ ($$$1 \le v_i, u_i \le n; 1 \le w_i \le 10^6$$$), где $$$v_i$$$ и $$$u_i$$$ — вершины, которые соединены ребром $$$i$$$, а $$$w_i$$$ — вес этого ребра.

Гарантируется, что сумма всех $$$n$$$ не превосходит $$$10^5$$$ ($$$\sum n \le 10^5$$$).

Выходные данные

Для каждого набора тестовых данных выведите ответ на него: минимальное количество ходов, необходимое, чтобы сделать сумму весов путей от корня до каждого листа не превосходящей $$$S$$$.

Пример
Входные данные
3
3 20
2 1 8
3 1 7
5 50
1 3 100
1 5 10
2 3 123
5 4 55
2 100
1 2 409
Выходные данные
0
8
3