Сеть
Input
file |
input.txt |
Output
file |
output.txt |
Time
limit |
1 секунда на тест |
Андрей работает системным администратором и планирует установить новую сеть в своей компании. В компании будет N хабов, которые могут быть соединены друг с другом с использованием кабелем. Так как каждый рабочий компании должен иметь доступ ко всей сети, поэтому каждый хаб должен быть доступен по кабелем с любого другого хаба (возможно, через некоторые промежуточные хабы).
Так как доступны кабели разных типов и более короткие являются более дешевыми, необходимо сделать такой план соединения хабов, чтобы максимальная длина используемого кабеля была минимальной. Есть другая проблема — не каждый хаб может быть соединен с каждым из-за проблем с совместимостью и геометрических ограничений. Конечно, Андрей предоставит Вам все необходимую информацию о возможных соединениях между кабелями.
Вам нужно помочь Андрею найти способ соединения хабов,
удовлетворяющий вышеприведенным условиям.
Входные данные
Первая строка входного файла содержит два целых числа: N — количество хабов в сети (2 £ N £ 1000) и M — количество возможных соединений между хабами (1 £ M £ 15000). Все хабы пронумерованы от 1 до N. Следующие M строк содержат информацию о возможных соединениях — номера двух хабов, которые могут быть соединены и длину кабеля, необходимую для их соединения. Длина – целое число, не превосходящее 106. Существует не более одного способа соединить два хаба. Хаб не может быть соединен сам с собой. Существует хотя бы один способ соединить все хабы.
Выходные данные
Выведите сначала максимальную длину кабеля в вашем плане соединения (величина, которую вы должны минимизировать). Затем выведите ваш план: сначала выведите P — количество используемых кабелей, затем выведите P пар целых чисел — номера хабов, соединяемых соответствующими кабелями. Разделяйте номера пробелами и/или переводами строки.
Пример
input.txt |
output.txt |
4 6 1 2 1 1 3 1 1 4 2 2 3 1 3 4 1 2 4 1 |
1 4 1 2 1 3 2 3 3 4 |