AT_njpc2017_e.限界集落

ゆらふなくん是一个位于深山中的“限界集落”村庄的村长。在这个村庄中，每一条道路都根据村里的规矩被指定了一个“吉利的通行方向”。如果有人违反村规，逆着吉利方向通行，就会受到村民们冷漠的目光。

这个限界集落由 $N$ 块土地和连接这些土地的 $N-1$ 条道路组成，每块土地编号为 $1,2,...,N$。第 $i$ 条道路（$1 \leq i \leq N-1$）连接土地 $A_i$ 和 $B_i$，这条道路的吉利通行方向是从 $A_i$ 到 $B_i$。在 $A_i$ 和 $B_i$ 之间移动需要 $C_i$ 分钟。以土地为顶点、道路为边构成的无向图是连通的。从一块土地到另一块土地所需的时间是经过的所有道路的 $C$ 之和。

ゆらふなくん打算为限界集落建一所学校。他希望无论从哪块土地出发，都能在 $D$ 分钟以内到达学校，以避免学生上学花费过长时间。同时，为了防止学生在上学途中受到村民冷漠的目光，可能需要调整部分道路的吉利通行方向。在满足上学时间限制的土地中，选择需要最少调整吉利通行方向的土地建校。请输出在这种情况下需要调整吉利通行方向的最小次数。如果不存在满足上学时间限制的土地，则输出 $-1$。

输入通过标准输入按以下格式给出。

$N$ $D$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\cdots$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$

请输出在满足上学时间限制的土地中，最少需要调整村规的次数。如果不存在满足上学时间限制的土地，则输出 $-1$。

限制条件

• 所有输入均为整数。
• $2 \leq N \leq 10^5$
• $1 \leq A_i, B_i \leq N$
• $A_i \neq B_i$
• 不存在 $i \neq j$ 使得 $A_i = A_j$ 且 $B_i = B_j$
• 不存在 $i \neq j$ 使得 $A_i = B_j$ 且 $A_j = B_i$
• $0 \leq C_i \leq 10^3$
• $1 \leq D \leq 10^9$
• 如果无视村规，则任意两块土地之间都可以通过若干道路连通。

样例说明 1

满足上学时间限制的土地为 2、4、5、6。它们分别需要最少 4、3、2、2 次调整村规。

由 ChatGPT 4.1 翻译