问题陈述
给你一个有偶数个节点的连通无向图。 连通图是所有节点通过边直接或间接连接的图。
你的任务是找到一棵边成本中值最小的生成树。 图的生成树是指包含图的所有节点的树。
输入
输入由多个数据集组成。
每个数据集的格式如下。
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