축제는 계속되어야 한다

큐브 나라는 도시 $N$개와 양방향 도로 $N-1$개로 이루어져 있다. 서로 다른 두 도시 사이에는 이동 경로가 항상 존재하므로 도로망은 트리이다. 도시에는 $1$번부터 $N$번까지, 도로에는 $1$번부터 $N-1$번까지 번호가 붙어 있고, $i$번 도로의 길이는 $l_i$이다.

큐브 나라의 통치자가 축제를 연다. 도로 $N-1$개 중에서 $M$개를 골라 고른 도로마다 자동차 퍼레이드나 체육 대회 같은 행사를 하나씩 연다. 교통이 마비된다는 교통부의 항의를 받아들여 통치자는 혼란을 줄이기로 했다. 도로 $M$개를 고르는 모든 방법 중에서, 고른 도로만 지나는 단순 경로의 길이 최댓값이 가장 작아지는 방법을 고른다. 경로의 길이는 그 경로에 있는 도로의 길이를 모두 더한 값이고, 도시 한 곳에 머무는 경로의 길이는 $0$이다.

각 테스트 케이스마다 이렇게 최소화한 최댓값을 구하라.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스의 첫째 줄에 정수 $N$과 $M$ ($2 \le N \le 2000$, $1 \le M \le N-1$)이 공백으로 구분되어 주어진다. $N$은 도시의 수, $M$은 골라야 하는 도로의 수이다. 이어지는 $N-1$개의 줄에 도로 정보가 주어진다. 그중 $i$번째 줄에는 정수 $a_i$, $b_i$, $l_i$ ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le l_i \le 10^6$)가 공백으로 구분되어 주어지며, $i$번 도로가 도시 $a_i$와 도시 $b_i$를 잇고 그 길이가 $l_i$라는 뜻이다.

모든 테스트 케이스의 $N$을 더한 값은 $2000$을 넘지 않는다.

각 테스트 케이스마다 고른 도로만 지나는 단순 경로의 길이 최댓값을 최소로 만들었을 때 그 값을 한 줄에 출력한다.

단순 경로는 같은 도시를 두 번 지나지 않는 경로이다. 즉 서로 다른 도시의 수열 $c_1, c_2, \dots, c_l$이며, $1 \le i \le l-1$인 모든 $i$에 대해 도시 $c_i$와 도시 $c_{i+1}$을 잇는 도로가 있어야 한다. 이 문제에서는 그 도로가 모두 고른 도로여야 한다.