|
В неком государстве имеется N городов. Было решено соединить их авиарейсами так, чтобы
из любого города можно было долететь до любого другого. При этом между некоторыми парами городов
рейсы организовать невозможно по тем или иным соображениям, а для всех остальных пар городов
заданы расстояния между ними. Требуется определить, между какими парами городов организовать авиарейсы,
чтобы их суммарная протяженность была минимальной.
Входные данные
В первой строке через пробел - два числа N и E - общее число городов и число пар городов, между которыми возможна организация рейсов.
В следующих E строках через пробел записаны по три числа - номер начального города,
конечного и расстояние между ними.
2<=N<=1000
Выходные данные
В первой строке - минимальная суммарная протяженность рейсов. В следующих N-1 строках - через пробел пары городов,
которые будут связаны рейсами.
Пример входных данных
4 5
1 2 3
1 3 4
2 3 2
2 4 1
3 4 8
Пример выходных данных
6
1 2
2 3
2 4
| 