Chia đôi trọng số cạnh

Cho một cây có gốc gồm $n$ đỉnh, đỉnh $1$ là gốc. Mỗi cạnh $i$ có trọng số $w_i$ (số nguyên dương).

Trọng số của đường đi từ đỉnh $u$ đến đỉnh $v$ là tổng trọng số các cạnh trên đường đi giữa hai đỉnh đó.

Bạn có thể thực hiện một dãy các phép biến đổi (có thể không thực hiện phép nào). Mỗi phép biến đổi: chọn một cạnh và chia trọng số của nó cho $2$, làm tròn xuống (nghĩa là $w_i:=\lfloor w_i/2\rfloor$).

Nhiệm vụ: tìm số phép biến đổi tối thiểu để tổng trọng số các đường đi từ gốc tới mỗi lá không vượt quá $S$. Tức là gọi $w(u,v)$ là trọng số đường đi từ $u$ tới $v$, cần đạt

$$\sum _{v\in \text{lá}}w(1,v)\le S.$$

Một đỉnh được gọi là lá nếu nó không có đỉnh con nào trong cây có gốc (đỉnh gốc không được coi là lá khi $n\ge 2$).

Bạn phải xử lý $t$ bộ dữ liệu độc lập.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ($1\le t\le 2·{10}^4$) — số bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng đầu chứa hai số nguyên $n$ và $S$ ($2\le n\le {10}^5$; $1\le S\le {10}^{16}$).
• $n-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $v_i$, $u_i$, $w_i$ ($1\le v_i,u_i\le n$; $1\le w_i\le {10}^6$) mô tả một cạnh nối hai đỉnh $v_i$ và $u_i$ với trọng số $w_i$.

Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên — số phép biến đổi tối thiểu cần thực hiện.

Ràng buộc

• $1\le t\le 2·{10}^4$
• $2\le n\le {10}^5$
• $1\le S\le {10}^{16}$
• $1\le w_i\le {10}^6$
• Tổng $n$ trên tất cả bộ dữ liệu không vượt quá ${10}^5$

Ví dụ