Problem Statement

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.

Input

The input consists of multiple datasets.

The format of each dataset is as follows.

$n$ $m$ $s_1$ $t_1$ $c_1$ ... $s_m$ $t_m$ $c_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.

Output

Print the median value in a line for each dataset.

Sample Input

Sorry, update sample3 dataset.(11:33)```plain

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

### Output for the Sample Input

```plain

5
2
421

Source Name

JAG Practice Contest for ACM-ICPC Asia Regional 2012