30052 - 网络

Andrew 是公司的系统管理员，正打算搭建一个新的网络。公司里有 N 个集线器（hub），它们可以通过电缆相互连接。因为每个员工都必须能访问整个网络，所以任何一个集线器都必须能通过电缆（可能经过中间的集线器）连接到其他集线器。

由于电缆有不同类型，且短的电缆更便宜，所以需要设计一个连接方案，使得单根电缆的最长长度尽可能短。另一个难题是——并非所有集线器都能直接连接，受限于兼容性和建筑结构。当然，Andrew 会给你所有可能连接的信息。

你的任务是帮 Andrew 找出一个连接方案，满足以上所有条件。

第一行包含两个整数：N —— 集线器数量（2 <= N <= 1000），M —— 可能的连接数（1 <= M <= 15000）。集线器编号从 1 到 N。接下来 M 行，每行给出一条可能的连接，格式是两个集线器编号和连接它们所需的电缆长度。长度是正整数，不超过 10^6。不会有重复连接，也不会有集线器连接自己。保证至少存在一种方案能连接所有集线器。

输入一直处理到文件末尾。

先输出你设计方案中单根电缆的最大长度（你要让它尽可能小）。然后输出所用电缆数 P，接着输出 P 行，每行两个整数，表示用电缆连接的两个集线器编号。数字之间用空格或换行分开均可。