트리 오델로
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

정점의 개수가 $$$N$$$개인 트리가 주어진다. 트리는 $$$1$$$번 정점을 루트로 하며, 간선의 개수는 $$$N−1$$$개이다.

트리의 각 간선에는 양의 가중치가 있으며, 두 정점 $$$u$$$, $$$v$$$ 사이의 거리는 $$$u$$$에서 $$$v$$$로 가는 단순 경로 위의 모든 간선 가중치 합으로 정의한다.

트리의 각 정점은 흰색이나 검은색 중 하나의 색을 가지며, 처음에는 트리의 모든 정점이 흰색이다. 이 트리에 대해 다음과 같은 연산을 사용할 수 있다.

  1. $$$0 \le k \le 10^9$$$인 정수 $$$k$$$를 하나 선택한다.
  2. 트리의 루트로부터 거리가 $$$k$$$ 이하인 모든 정점의 색을 흑백 반전한다. 즉, 정점이 흰색이라면 검은색으로, 검은색이라면 흰색으로 바꾼다.

이 연산을 최대 $$$N$$$번 사용하여, 트리에서 검은색인 정점의 개수를 정확히 $$$M$$$개로 만들 수 있는지 구해보자. 연산 횟수는 최소일 필요가 없지만, 반드시 $$$N$$$번 이하이어야 한다.

Input

첫 번째 줄에 정수 $$$N$$$, $$$M$$$이 공백으로 구분되어 주어진다.

다음 $$$N-1$$$개의 줄에는 간선의 정보가 주어진다. 그중 $$$i$$$번째 줄에는 정수 $$$u_i,v_i, x_i$$$가 공백으로 구분되어 주어진다. 이는 $$$u_i$$$번 정점과 $$$v_i$$$번 정점을 잇는 간선의 가중치가 $$$x_i$$$임을 의미한다.

Output

만약 검은색인 정점이 정확히 $$$M$$$개가 될 수 있다면

만약 검은색인 정점이 정확히 $$$M$$$개가 될 수 없다면 첫 번째 줄에 -1을 출력한다.

Examples

Input
4 3
1 2 3
1 3 1
4 3 2
Output
3
0 1 3
Input
5 2
1 2 10
1 3 10
1 4 10
1 5 10
Output
-1

Note