Far Far Away

어느 대학의 강사들은 하루 대부분을 일하며 보낸다. 쉴 수 있는 시간은 학회나 세미나 같은 학술 행사로 이동하는 동안뿐인데, 이동 시간도 근무 시간으로 치기 때문이다. 그래서 강사들은 이동 시간을 잠자는 데 쓰기로 했고, 참석할 행사를 고를 수 있을 때는 언제나 대학에서 가장 먼 곳을 고른다. 게다가 까다로워서 총 이동 시간이 $M$ 이상일 때만 출발한다.

지도는 1번부터 $C$번까지 번호가 붙은 도시와 도시 사이의 일방통행 항공편으로 이루어진다. 대학은 1번 도시에 있고, 모든 도시에서 학술 행사가 열리므로 어느 도시나 목적지가 된다. 목적지까지 가려면 보통 다른 도시를 여러 개 거쳐야 한다. 1번을 뺀 모든 도시에는 들어오는 항공편이 정확히 하나씩 있다. 즉 지도는 1번 도시를 뿌리로 하는 방향 트리이고, 1번 도시에서 나머지 모든 도시로 갈 수 있다. 항공편은 어떤 순서로든 주어진다.

각 테스트 케이스마다 1번 도시에서 출발하는 가장 긴 경로의 이동 시간을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($0 < T \le 20$).

각 테스트 케이스의 첫 줄에는 두 정수 $C$와 $M$이 주어진다. $C$는 도시의 수 ($1 < C \le 100000$), $M$은 까다로움 기준값, 곧 여행할 가치가 있다고 보는 최소 이동 시간이다 ($1 \le M \le 100000000$). 이어지는 $C-1$개의 줄에는 각각 세 정수 $C_1$, $C_2$, $D$가 주어진다. 이는 $C_1$번 도시에서 $C_2$번 도시로 가는 이동 시간 $D$의 일방통행 항공편을 뜻한다 ($1 \le C_1, C_2 \le C$, $0 < D \le 100$).

입력의 모든 값은 정수이고, 한 줄에 정수가 여러 개 있으면 공백 하나로 구분한다.

각 테스트 케이스마다 한 줄에 답을 하나 출력한다. 1번 도시에서 출발하는 가장 긴 경로의 이동 시간을 출력한다. 1번 도시에서 어디로 가도 이동 시간이 $M$ 이상인 경로가 없으면 대신 -1을 출력한다.