巨木之森

题号：NC209864
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

调查兵团第56次壁外调查将对巨木之森展开，已知巨木之森共有 $n$ 块区域和 $n-1$ 条道路，保证这 $n$ 块区域联通。为了调查结果尽可能准确，兵团会派遣若干支小分队调查巨木之森，派出的小分队需满足以下规定：

1.每支小分队都可以选择从任意一块区域出发，但各支小分队的出发区域必须互不相同。

2.每支小分队都必须遍历完 $n$ 块区域。

3.每支小分队的物资消耗量为其遍历完 $n$ 块区域的路程和。

现已知调查兵团的物资总量为 $m$ ，请问最多能派遣多少支小分队参与调查？

第一行两个正整数 $n$ 与 $m$ ，表示巨木之森的区域数和调查兵团的物资总量，其中： $n\leq10^{5}$ ， $m\leq10^{18}$ 。

接下来 $n-1$ 行，每行三个正整数 $u$ , $v$ , $w$ ，表示 $u$ 号区域和 $v$ 号区域之间有一条长为 $w$ 的道路。其中： $u\leq n$ ， $v\leq n$ ， $w\leq10^{8}$ 。

输出最多能派遣的小分队数量。

示例1

复制

3 6
1 2 1
2 3 1

复制

从1号区域出发，遍历完3块区域，物资消耗量最少为2。

从2号区域出发，遍历完3块区域，物资消耗量最少为3。

从3号区域出发，遍历完3块区域，物资消耗量最少为2。

故最多派遣2支小分队。