Minimum-Edge k-Sum Path in a Tree

Given a tree with weighted edges, find a simple path (a path that does not repeat any vertex) such that the sum of the edge weights equals \(k\) and the number of edges in the path is minimized. If no such path exists, output -1.

Note: A tree with n vertices has exactly n - 1 edges, and every simple path is unique between two vertices.

inputFormat

The first line contains two integers n and k, where n is the number of vertices in the tree and k is the target sum of edge weights.

Each of the next n - 1 lines contains three integers u, v, and w indicating that there is an undirected edge between vertices u and v with weight w.

outputFormat

Output a single integer: the minimum number of edges in a simple path whose sum of edge weights equals \(k\). If no such path exists, output -1.

sample

3 3
1 2 1
2 3 2

2