#169. 2599. [IOI2011]Race

2599. [IOI2011]Race

[IOI2011] Race

题目描述

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

输入格式

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

接下来 n1n-1 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,代表有一条连接 uiu_iviv_i,边权为 wiw_i 的无向边。

注意:点从 00 开始编号

输出格式

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

如果不存在这样的路径,输出 1-1

样例 #1

样例输入 #1

4 3
0 1 1
1 2 2
1 3 4

样例输出 #1

2

提示

对于 100%100\% 的数据,保证 1n2×1051\leq n\leq 2\times10^51k,wi1061\leq k,w_i\leq 10^60ui,vi<n0\leq u_i,v_i<n