Сеть

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