You are given a connected undirected graph which has even numbers of nodes. A connected graph is a graph in which all nodes are connected directly or indirectly by edges.

Your task is to find a spanning tree whose median value of edges' costs is minimum. A spanning tree of a graph means that a tree which contains all nodes of the graph.

The input consists of multiple datasets.

The format of each dataset is as follows.

nms_1t_1c_1...s_mt_mc_m

The first line contains an even number `n` (`2 \leq n \leq 1,000`) and an integer `m` `(n-1 \leq m \leq 10,000)`.
`n` is the nubmer of nodes and `m` is the number of edges in the graph.

Then `m` lines follow, each of which contains `s_i` (`1 \leq s_i \leq n`), `t_i` (`1 \leq s_i \leq n, t_i \neq s_i`) and `c_i` (`1 \leq c_i \leq 1,000`).
This means there is an edge between the nodes `s_i` and `t_i` and its cost is `c_i`.
There is no more than one edge which connects `s_i` and `t_i`.

The input terminates when `n=0` and `m=0`.
Your program must not output anything for this case.

Print the median value in a line for each dataset.

2 1 1 2 5 4 6 1 2 1 1 3 2 1 4 3 2 3 4 2 4 5 3 4 6 8 17 1 4 767 3 1 609 8 3 426 6 5 972 8 1 607 6 4 51 5 1 683 3 6 451 3 4 630 8 7 912 3 7 43 4 7 421 3 5 582 8 4 538 5 7 832 1 6 345 8 2 608 0 0

5 2 421

Source: JAG Practice Contest for ACM-ICPC Asia Regional 2012
, Japan, 2012-11-04

http://jag-icpc.org/

http://jag2012autumn.contest.atcoder.jp/

http://jag-icpc.org/

http://jag2012autumn.contest.atcoder.jp/