题目描述

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

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

输入格式

第一行两个整数 $\red {N, K}$。

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

输出格式

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

如果不存在满足要求的路径，输出$\red {-1}$。

样例

输入样例

4 3
0 1 1
1 2 2
1 3 4

输出样例

2

提示

$\red {N≤200000,K≤1000000}$