题目描述

给定一个有偶数个节点的无向连通图。

你的任务是找到一个生成树，它的边代价的中值是最小的（图的生成树是指包含图的所有节点的树）。

输入格式

每组数据第一行两个数 $n,m$，代表无向连通图中点的数量与边的数量。

接下来 $m$ 行每行三个数 $u,v,w$，代表 $u$ 和 $v$ 之间有一条权值为 $w$ 的边。

当 $n,m=0$ 时读入结束。

输出格式

对于每组数据，一行输出一个数，代表该生成树中边代价的中值。

输入输出样例

输入#1

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

输出#1

5
2
421