ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1416. Для служебного пользования…

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Зафод Билброкс — президент имперского галактического правительства. И совершенно случайно владеет предприятием, торгующим подержанными шариковыми ручками. Это сложный, высокодоходный и высоко конкурентный бизнес. Чтобы остаться лидером, приходится постоянно минимизировать издержки, чему замечательно помогает пост президента. Только нужно сохранять этот бизнес в тайне. Как президент, Зафод имеет доступ к чрезвычайно секретным и важным данным — точным затратам энергии на гиперпространственные переходы между планетами. Конечно, эта информация чрезвычайно полезна для его компании. Зафоду необходимо выбрать между планетами наименьшее возможное число переходов, так, чтобы с любой планеты на любую можно было попасть по выбранным переходам и суммарная стоимость переходов была минимальна. Задача несложная, если бы не надо было сохранять в тайне, что Зафод помогает своей компании секретной информацией. Поэтому Зафод решил найти не минимальный по стоимости вариант, а сразу следующий. Как рачительный хозяин, он хочет оценить всё же потерю в деньгах вследствие конспирации.

Исходные данные

В первой строке записаны целые числа n и m — число планет в галактике и число гиперпереходов между ними (2 ≤ n ≤ 500; 1 ≤ mn (n − 1) / 2). Следующие m строк описывают эти гиперпереходы. i-я из них содержит целые числа ai, bi, wi, означающие, что между планетами ai и bi в обе стороны есть переход стоимостью wi единиц энергии (1 ≤ ai, bin; 0 ≤ wi ≤ 1000). Существует не более одного перехода между любыми двумя планетами. С любой планеты галактики можно попасть на любую другую посредством переходов.

Результат

Выдайте минимальный и следующий по затратам энергии набор переходов. Если существует несколько вариантов наборов переходов, выведите любой. Если какого-то из переходов не существует, обозначьте это стоимостью −1.

Примеры

исходные данныерезультат
4 6
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
2 4 1
Cost: 4
Cost: 4
3 2
1 2 2
2 3 2
Cost: 4
Cost: -1
Автор задачи: Ден Расковалов
Источник задачи: Чемпионат Уральского государственного университета, 29 октября 2005