경주

경주대회 IOR을 위해 가장 적합한 경주 코스를 찾으려 한다.

한 지역에 $N$개의 도시가 있고, $N-1$개의 고속도로가 이 도시들을 연결한다. 각 고속도로는 양방향이며 서로 다른 두 도시를 연결하고, 그 길이는 킬로미터 단위의 정수이다. 임의의 두 도시는 정확히 하나의 경로로만 연결된다. 즉, 도시와 고속도로는 하나의 트리를 이룬다.

경주 코스는 서로 다른 출발 도시와 도착 도시를 잇는 경로이며, 전체 길이가 정확히 $K$킬로미터여야 한다. 충돌을 막기 위해 어떤 고속도로도 두 번 이상 사용하지 않는다(따라서 어떤 도시도 두 번 이상 방문하지 않는다). 트리에서 두 도시를 잇는 경로는 유일하므로 이 조건은 자동으로 만족된다.

교통 체증을 줄이기 위해, 전체 길이가 정확히 $K$인 경로들 중에서 사용하는 고속도로(간선)의 수가 가장 적은 경로를 찾아야 한다.

도시는 $0$번부터 $N-1$번까지 번호가 매겨진다. 고속도로가 잇는 도시 번호는 $0$ 이상 $N-1$ 이하이고, 고속도로의 길이는 0 이상 1,000,000 이하의 정수이다. 모든 도시는 서로 연결되어 있다.

전체 길이가 정확히 $K$인 경로 중에서 고속도로 수가 가장 적은 경로의 고속도로 수를 출력한다. 그런 경로가 존재하지 않으면 $-1$을 출력한다.

첫째 줄에 도시의 수 $N$과 경주 코스의 길이 $K$가 공백으로 구분되어 주어진다.

이어지는 $N-1$개의 줄에는 각 고속도로의 정보가 주어진다. 각 줄에는 세 정수 $u$, $v$, $w$가 주어지며, 이는 도시 $u$와 도시 $v$를 잇는 길이 $w$의 고속도로를 뜻한다.

전체 길이가 정확히 $K$인 경로 중 고속도로 수가 가장 적은 경로의 고속도로 수를 한 줄에 출력한다. 그런 경로가 없으면 $-1$을 출력한다.