|
Главные дороги
(Время: 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.TXT | OUTPUT.TXT |
|---|
| 1 | 6 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 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
