Description

Given a tree with a weight on each edge, find a simple path whose total weight equals $k$, with the minimum possible number of edges.

Input Format

The first line contains two integers $n, k$, representing the number of vertices in the tree and the target path sum.

Each of the next $n-1$ lines contains three integers $u_i, v_i, w_i$, representing an undirected edge between $u_i$ and $v_i$ with weight $w_i$.

Note: vertices are numbered starting from $0$.

Output Format

Output a single integer, the minimal number of edges.

If no such path exists, output $-1$.

4 3
0 1 1
1 2 2
1 3 4

2

Hint

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 2 \times 10^5$, $0 \leq k, w_i \leq 10^6$, $0 \leq u_i, v_i < n$.

Translated by ChatGPT 5