Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Главные дороги

(Время: 5 сек. Память: 32 Мб Сложность: 82%)

Город, в котором живет Гоша, имеет N перекрестков, некоторые из которых соединены дорогами. По каждой дороге разрешено движение в обоих направлениях. Каждый день Гоша ездит на машине из дома на работу и обратно. Но дороги в городе, где живет Гоша, не очень хорошие, они часто портятся, и приходится их ремонтировать. Гоша заметил, что когда некоторые дороги закрывают на ремонт, часто он все равно может доехать из дома до работы за то же время, что в случае, когда ни одна дорога на ремонт не закрыта. С другой стороны, встречаются дороги такие, что когда они закрываются на ремонт, то время, которое требуется Гоше, чтобы добраться от дома до работы, увеличивается. А иногда Гоша просто не может доехать от дома до работы на машине. Такие дороги Гоша называет главными.

Помогите Гоше найти все главные дороги в городе.

Входные данные

Первая строка входного файла INPUT.TXT содержит N и M – количество перекрестков и дорог в городе, соответственно (2 ≤ N ≤ 20 000, 1 ≤ M ≤ 100 000). Гоша живет около перекрестка 1, а работает у перекрестка N.

Следующие M строк содержат информацию о дорогах. Каждая дорога описывается двумя перекрестками, которые она соединяет, и временем, которое необходимо Гоше, чтобы проехать по этой дороге от одного конца до другого. Время проезда по дороге – натуральное число, не превышающее 100 000. Между парой перекрестков может быть несколько дорог, но никакая дорога не соединяет перекресток с самим собой.

Гарантируется, что если все дороги доступны, Гоша может добраться от дома до работы.

Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите K – количество главных дорог. На второй строке выведите K чисел – номера главных дорог. Дороги пронумерованы от 1 до M в том порядке, в котором они заданы во входном файле.

Пример

INPUT.TXTOUTPUT.TXT
16 7
1 2 1
2 3 1
2 5 3
1 3 2
3 5 1
2 4 1
5 6 2
2
5 7

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2019, E-mail: admin@acmp.ru