[IOI2011]Race

题目描述

给一棵树,每条边有权。求一条简单路径,权值和等于 $k$,且边的数量最小。

输入输出格式

输入格式


第一行包含两个整数 $n,k$,表示树的大小与要求找到的路径的边权和。 接下来 $n-1$ 行,每行三个整数 $u_i,v_i,w_i$,代表有一条连接 $u_i$ 与 $v_i$,边权为 $w_i$ 的无向边。 **注意:点从 $0$ 开始编号**。

输出格式


输出一个整数,表示最小边数量。 如果不存在这样的路径,输出 $-1$。

输入输出样例

输入样例 #1

4 3
0 1 1
1 2 2
1 3 4

输出样例 #1

2

说明

对于 $100\%$ 的数据,保证 $1\leq n\leq 2\times10^5$,$1\leq k,w_i\leq 10^6$,$0\leq u_i,v_i<n$。