최소 중앙값 스패닝 트리

노드 수가 짝수인 연결 무향 그래프가 주어진다. 연결 그래프는 모든 노드가 간선을 따라 직접 또는 다른 노드를 거쳐 이어진 그래프다.

이 그래프의 스패닝 트리 중 간선 비용의 중앙값이 가장 작은 것을 찾아 그 중앙값을 구한다. 스패닝 트리는 그래프의 모든 노드를 포함하는 트리다.

$n$이 짝수이므로 스패닝 트리의 간선은 $n-1$개, 즉 홀수 개다. 간선 비용을 오름차순으로 정렬했을 때 앞에서 $n/2$번째 값이 중앙값이다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

n m
s1 t1 c1
...
sm tm cm

첫 줄에는 짝수 $n$ ($2 \le n \le 1000$)과 정수 $m$ ($n-1 \le m \le 10000$)이 주어진다. $n$은 노드 수, $m$은 간선 수다.

이어지는 $m$개의 줄에는 $s_i$, $t_i$, $c_i$가 주어진다 ($1 \le s_i \le n$, $1 \le t_i \le n$, $s_i \ne t_i$, $1 \le c_i \le 1000$). 노드 $s_i$와 $t_i$를 잇는 비용 $c_i$의 간선이 있다는 뜻이다. 같은 두 노드를 잇는 간선은 두 개 이상 주어지지 않는다. 각 데이터셋의 그래프는 연결 그래프다.

$n$과 $m$이 모두 $0$인 줄에서 입력이 끝난다. 이 줄에 대해서는 아무것도 출력하지 않는다.

각 데이터셋마다 중앙값을 한 줄에 출력한다.