问题陈述

给定一个连通的无向图，其中节点数量为偶数。连通图是指所有节点都通过边直接或间接相连。

你的任务是找到一个生成树，使得边的权重的中位数最小。生成树是指包含图的所有节点的树。

输入

输入包含多个数据集。

每个数据集的格式如下。

$n$ $m$ $s_1$ $t_1$ $c_1$ ... $s_m$ $t_m$ $c_m$

第一行包含一个偶数$n$ ($2 \leq n \leq 1,000$) 以及整数 $m$ $(n-1 \leq m \leq 10,000)$. $n$ 是节点数量，$m$ 是图中边的数量。

然后是 $m$ 行，每行包含 $s_i$ ($1 \leq s_i \leq n$), $t_i$ ($1 \leq s_i \leq n, t_i \neq s_i$) 和 $c_i$ ($1 \leq c_i \leq 1,000$)。表示节点 $s_i$ 和 $t_i$ 之间有一条边，其权重为 $c_i$。没有多于一条的边连接 $s_i$ 和 $t_i$。

当 $n=0$ 且 $m=0$ 时，输入终止。对于这种情况，你的程序不应输出任何内容。

输出

对于每个数据集，在一行中打印中位数的值。

示例输入

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

来源

JAG Practice Contest for ACM-ICPC Asia Regional 2012