← 返回题目列表

AtCoder · icpc2012autumn_c

C. 中值树

中文机器翻译题面 查看原题

问题陈述

给你一个有偶数个节点的连通无向图。 连通图是所有节点通过边直接或间接连接的图。

你的任务是找到一棵边成本中值最小的生成树。 图的生成树是指包含图的所有节点的树。


输入

输入由多个数据集组成。

每个数据集的格式如下。

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。 对于这种情况,您的程序不得输出任何内容。

输出

在一行中打印每个数据集的中值。


示例输入

抱歉,请更新sample3 数据集。(11:33)
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