[IOI2011] Race

题目描述

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

输入格式

第一行包含两个整数 $n,k$，表示树的大小与要求找到的路径的边权和。

接下来 $n-1$ 行，每行三个整数 $u_i,v_i,w_i$，代表有一条连接 $u_i$ 与 $v_i$，边权为 $w_i$ 的无向边。

注意：点从 $0$ 开始编号。

输出格式

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

如果不存在这样的路径，输出 $-1$。

样例 #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$。