题目描述

给定一棵 $N$个节点的树，每条边带有一个权值。

求一条简单路径，路径上各条边的权值和等于$K$，且路径包含的边的数量最少。

输入格式

第一行两个整数 $N,K$。

第 2∼$N$ 行每行三个整数 $x,y,z$，表示一条无向边的两个端点$x,y$和权值$z$，点的编号从 0 开始。

输出格式

输出一个整数，表示最少边数量。

如果不存在满足要求的路径，输出 −1。

样例

4 3
0 1 1
1 2 2
1 3 4

2

数据范围

$1≤N≤2×10^5, 1≤K≤10^6, 0≤z≤10^6$

来源

• IOI 2011
• BZOJ2599
• 算法竞赛进阶指南