Minimum Median Spanning Tree

You are given a connected undirected graph whose number of nodes is even. In a connected graph every node reaches every other node along edges, either directly or through other nodes.

Among all spanning trees of the graph, find the one whose median edge cost is smallest and report that median. A spanning tree is a tree that contains every node of the graph.

Because $n$ is even, a spanning tree has $n-1$ edges, an odd count. Sort those costs in non-decreasing order; the median is the value in position $n/2$.

The input consists of several datasets. Each dataset has this format.

n m
s1 t1 c1
...
sm tm cm

The first line holds an even number $n$ ($2 \le n \le 1000$) and an integer $m$ ($n-1 \le m \le 10000$). Here $n$ is the number of nodes and $m$ is the number of edges.

Each of the next $m$ lines holds $s_i$, $t_i$ and $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$). This means an edge of cost $c_i$ joins nodes $s_i$ and $t_i$. No two edges join the same pair of nodes. The graph of every dataset is connected.

The input ends with a line where $n$ and $m$ are both $0$. Print nothing for that line.

For each dataset, print the median on its own line.