题目描述

安德鲁是系统管理员，计划为公司搭建新网络。公司有$N$个集线器，需要用网线连接。为确保每个员工能访问整个网络，所有集线器必须连通（可通过中间集线器转接）。

由于网线类型多样且越短越便宜，需要设计连接方案，使得单根网线的最大长度最小。此外，部分集线器因兼容性或建筑限制无法直接连接。安德鲁会提供所有可能的连接信息，你需要帮他找到满足条件的方案。

输入格式

第一行：两个整数$N$（$2≤N≤1000$，集线器数量）和$M$（$1≤M≤15000$，可能的连接数）。
接下来M行：每行三个整数$A、B、L$，表示集线器A和B可连接，所需网线长度为$L（1≤L≤10⁶）$。
保证任意两集线器最多一种连接方式，无自环，且至少存在一种连通方案。

输出格式

第一行：方案中单根网线的最大长度（即需最小化的值）。
第二行：使用的网线数量P。
接下来P行：每行两个整数，表示连接的两集线器编号。

输入示例 1

4 6  
1 2 1  
1 3 1  
1 4 2  
2 3 1  
3 4 1  
2 4 1  

输出示例 1

1  
4  
1 2  
1 3  
2 3  
3 4  

来源

Northeastern Europe $2001$, Northern Subregion