[IOI2011]Race

题目描述

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

输入输出格式

输入格式


第一行包含两个整数 $n, K$。 接下来 $n - 1$ 行,每行包含三个整数,表示一条无向边的两端和权值。 注意点的编号从 $0$ 开始。

输出格式


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

输入输出样例

输入样例 #1

4 3
0 1 1
1 2 2
1 3 4

输出样例 #1

2

说明

保证 $n \leqslant 2 \times 10^5,$ $K \leqslant 10^6$。