Занятие 15

Андрей работает системным администратором и планирует создание новой сети в своей компании. Всего будет `N` хабов, они будут соединены друг с другом с помощью кабелей.

Поскольку каждый сотрудник компании должен иметь доступ ко всей сети, каждый хаб должен быть достижим от любого другого хаба – возможно, через несколько промежуточных хабов. Поскольку имеются кабели различных типов и короткие кабели дешевле, требуется сделать такой план сети (соединения хабов), чтобы максимальная длина одного кабеля была как можно меньшей. Есть еще одна проблема – не каждую пару хабов можно непосредственно соединять по причине проблем совместимости и геометрических ограничений здания. Андрей снабдит вас всей необходимой информацией о возможных соединениях хабов.

Вы должны помочь Андрею найти способ соединения хабов, который удовлетворит всем указанным выше условиям.

Первая строка входного файла содержит два целых числа: `N` – количество хабов в сети (`2\ ≤\ N\ ≤\ 1000`) и `M` – количество возможных соединений хабов (`1\ ≤\ М\ ≤\ 15\ 000`). Все хабы пронумерованы от 1 до `N`. Следующие `M` строк содержат информацию о возможных соединениях – номера двух хабов, которые могут быть соединены, и длина кабеля, который требуется, чтобы соединить их. Эта длина – натуральное число, не превышающее `10^6`. Существует не более одного способа соединить каждую пару хабов. Хаб не может быть присоединен сам к себе. Всегда существует хотя бы один способ соединить все хабы.

Сначала выведите максимальную длину одного кабеля в вашем плане соединений (это величина, которую вы должны минимизировать). Затем выведите свой план: сначала выведите `P` – количество кабелей, которые вы использовали, затем выведите `P` пар целых чисел – номера хабов, непосредственно соединенных в вашем плане кабелями.

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

1
3
1 2
1 3
3 4